单调队列88分求调
  • 板块P1714 切蛋糕
  • 楼主ZeroHead
  • 当前回复0
  • 已保存回复0
  • 发布时间2025/1/3 15:00
  • 上次更新2025/1/3 20:21:32
查看原帖
单调队列88分求调
1435392
ZeroHead楼主2025/1/3 15:00
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int inf=1e18;
const int MAXN=5e5+5;
int n,m,a[MAXN],q[MAXN],pre[MAXN];
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        pre[i]=pre[i-1]+a[i];
    }
    int h=1,t=0;
    int ans=-inf;
    for(int i=0;i<=n;i++){
        while(h<=t && i>=q[h]+m) h++;
        while(h<=t && pre[i]<=pre[q[t]]) t--;
        q[++t]=i;
        ans=max(ans,pre[i+1]-pre[q[h]]);
    }
    cout<<ans<<endl;
    return 0;
}
2025/1/3 15:00
加载中...