WA#1&TLE*3求指正思路
  • 板块P1714 切蛋糕
  • 楼主LucAlva
  • 当前回复0
  • 已保存回复0
  • 发布时间2025/6/15 17:12
  • 上次更新2025/6/16 17:13:38
查看原帖
WA#1&TLE*3求指正思路
1044970
LucAlva楼主2025/6/15 17:12
#include <bits/stdc++.h>
using namespace std;
struct aaa{
    int a,b;
};
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    long long p[n+10]{},s[n+10]{},sss=-1e9; 
    for(int i=1;i<=n;i++){
        scanf("%lld",&p[i]);
        s[i]=s[i-1]+p[i];
        sss=max(sss,p[i]);
    }
    deque <aaa> a;
    int ii=1;
    for(int i=1;i<=n;i++){
        if(!a.empty()&&a.back().b-a.front().b==m-1){
            a.pop_front();
        }
		a.push_back({p[i],i});
        deque <aaa> b=a;
        while(!a.empty()&&a.front().a<=0){
			a.pop_front();
		}
		while(!a.empty()&&a.back().a<=0){
			a.pop_back();
		}
        if(!a.empty()&&a.size()!=1) sss=max(sss,s[a.back().b]-s[a.front().b-1]);
        a=b;
    }
    printf("%lld",sss);
    return 0;
}
2025/6/15 17:12
加载中...