请求添加HACK数据
  • 板块P1714 切蛋糕
  • 楼主zpy12345
  • 当前回复1
  • 已保存回复2
  • 发布时间2024/4/9 20:52
  • 上次更新2024/4/9 22:55:17
查看原帖
请求添加HACK数据
920886
zpy12345楼主2024/4/9 20:52

(这题的数据太水了)

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;
}
2024/4/9 20:52
加载中...