单调队列求调 80pts,不知道哪里错了
查看原帖
单调队列求调 80pts,不知道哪里错了
400468
Aakkosetsumussa楼主2023/7/17 10:38
#include<bits/stdc++.h>
using namespace std;
int n,k,a[1000005],q[1000005],sum[1000005],ans=-1e7;
int head=0,tail=0;
int main() {
	cin>>n>>k;
	for(int i=1; i<=n; i++) cin>>a[i],sum[i]=sum[i-1]+a[i];
	for(int i=1; i<=n; i++) {
		while(head<tail&&q[head]+k<=i) head++;
		while(head<tail&&sum[q[tail-1]]>sum[i]) tail--;
		q[tail++]=i;
		//cout<<sum[q[head]]<<" ";
		ans=max(ans,sum[i+1]-sum[q[head]]);
	}
	//cout<<endl;
	cout<<ans;
	return 0;
}//1 3 6 10 15
2023/7/17 10:38
加载中...