ST表RE求调
  • 板块P1714 切蛋糕
  • 楼主yaoshuen
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/10/7 18:12
  • 上次更新2024/10/7 20:32:46
查看原帖
ST表RE求调
916086
yaoshuen楼主2024/10/7 18:12
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e5+20;
int n,m;
int a[N];
int s[N];
int st[N<<1][30];
int query(int L,int R){
	int p=log2(R-L+1);
	return min(st[L][p],st[R-(1<<p)+1][p]);
}
int ans;
signed main(){
	scanf("%lld%lld\n",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%lld",a+i);
		s[i]=s[i-1]+a[i];
		st[i][0]=s[i];
	}
	st[0][0]=0;
	if(m==0){
		printf("0\n");
		exit(0);
	}
	for(int i=1;i<=27;i++){
		for(int j=0;j<=n&&j+(1<<(i-1))<=n;j++){
			st[j][i]=min(st[j][i-1],st[j+1<<(i-1)][i-1]);
		}
	}
	ans=-1;
	for(int i=1;i<=n;i++){
		ans=max(ans,s[i]-query((int)(max(0ll,i-m)),i-1));
	}
	printf("%lld\n",ans);
	return 0;
}

2024/10/7 18:12
加载中...