蒟蒻求助!没有使用前缀和的单调队列来做的这道题。不知道为什么有一个数据点一直过不了,自己检查没发现错误,求大佬帮助!
#include<bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n,m;
cin>>n>>m;
vector<int> a(n+1,0);
for(int i=1;i<=n;i++){
cin>>a[i];
}
vector<int> q(500005);
int sum=0,h=1,t=0,ans=-1000000;
for(int i=1;i<=n;i++){
while(t>=h&&h+m<=i){
sum-=a[q[h]];h++;
ans=max(ans,sum);
}
while(t>=h&&a[q[h]]<=0){
sum-=a[q[h]];h++;
ans=max(ans,sum);
}
while(t>=h&&a[i]+sum<=0){
sum-=a[q[h]];
h++;
ans=max(ans,sum);
}
q[++t]=i;
sum+=a[i];
ans=max(ans,sum);
}
cout<<ans<<endl;
return 0;
}