60分求助
  • 板块P1714 切蛋糕
  • 楼主ywsh27
  • 当前回复0
  • 已保存回复0
  • 发布时间2022/5/22 23:48
  • 上次更新2023/10/28 00:48:12
查看原帖
60分求助
186138
ywsh27楼主2022/5/22 23:48
#include<bits/stdc++.h>
using namespace std;
#define int long long
int a[100001],n,m,now,dp[100001][25],ans,lg[100001],Q_L,Q_R;
void RMQ_pre()
{
	for(int i=1;i<=n;++i)dp[i][0]=a[i];
	for(int j=1;(1<<j)<=n;++j)
		for(int i=1;i+(1<<j)-1<=n;++i)
			dp[i][j]=min(dp[i][j-1],dp[i+(1<<j-1)][j-1]);
}
signed main()
{
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n;++i)scanf("%lld",&now),ans=max(ans,now),a[i]=a[i-1]+now;
	RMQ_pre();
	lg[0]=-1;
	for(int i=1;i<=n;++i)lg[i]=lg[i>>1]+1;
	for(int i=1;i<=n;++i)
	{
		if(i-m>0)Q_L=i-m;
		else Q_L=0;
		Q_R=i-1;
		int len=lg[Q_R-Q_L+1];
		int min_sum=min(dp[Q_L][len],dp[Q_R-(1<<len)][len]);
		ans=max(ans,a[i]-min_sum);
	}
	cout<<ans;
    return 0;
}
2022/5/22 23:48
加载中...