(这题的数据太水了)
5 5
-1 -1 -1 -1 -1
输出:-1
诸如此类全是负数的测试点(厄运蛋糕)可以卡掉特判有误的一些提交,例如这个实际是错误的,但过了:
#include<bits/stdc++.h>
using namespace std;
int n,m,a[500001],b[500001],q[500001];
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>a[i];
b[i]=b[i-1]+a[i];
}
int l=0,r=0;
int ans=-1e9;
for(int i=0;i<=n;i++)
{
if(l<r&&q[l]+m<i) l++;
while(l<r&&b[q[r-1]]>b[i])r--;
q[r]=i;
r++;
ans=max(ans,b[i]-b[q[l]]);
}
cout<<ans<<endl;
return 0;
}