有一个数据点过不了!!求助!!
  • 板块P1714 切蛋糕
  • 楼主tanyalee
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/3/31 17:24
  • 上次更新2023/10/23 19:57:10
查看原帖
有一个数据点过不了!!求助!!
896128
tanyalee楼主2023/3/31 17:24

蒟蒻求助!没有使用前缀和的单调队列来做的这道题。不知道为什么有一个数据点一直过不了,自己检查没发现错误,求大佬帮助!

#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;
}
2023/3/31 17:24
加载中...