76求条
  • 板块P1714 切蛋糕
  • 楼主cxlqwq
  • 当前回复4
  • 已保存回复4
  • 发布时间2024/11/2 10:00
  • 上次更新2024/11/2 10:19:16
查看原帖
76求条
1319065
cxlqwq楼主2024/11/2 10:00
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=5e5+5;
ll sum[N],a[N],n,k,q[N];
int tail=-1,head=0;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>k;
    for(int i=1;i<=n;i++){
    	cin>>sum[i];
    	sum[i]+=sum[i-1];
	}
	ll res=-1999999999;
	for(int i=1;i<n;i++){
		while(tail>=head&&sum[i-1]<=sum[q[tail]]){
			tail--;
		}
		q[++tail]=i-1;
		while(tail>=head&&q[head]<i-k){
			head++;
		}
		int j=q[head];
		res=max(res,sum[i]-sum[j]);
	}
	cout<<res<<'\n';
	return 0;
}

2024/11/2 10:00
加载中...