[普及2][小埋的生日蛋糕]WA90

[黄思焰]

前缀和计算前i个的幸运综合
单调队列维护i前面i-m~i-1之间最小的幸运值
sum[i]-sum[队首]更新答案

#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[500010],sum[500010],ans=-1e9;
deque<int>q;
int main(){
  cin>>n>>m;
  for(int i=1;i<=n;i++){
    cin>>a[i];
  }
  for(int i=1;i<=n;i++) sum[i]=sum[i-1]+a[i];
  q.push_back(1);
  for(int i=2;i<=n;i++){
    while(!q.empty()&&i-q.front()>m) q.pop_front();
    if(!q.empty()) ans=max(ans,sum[i]-sum[q.front()]);
    while(!q.empty()&&sum[q.back()]>sum[i]) q.pop_back();
    q.push_back(i);
  }
  cout<<ans;
  return 0;
}

[蒋昀珀]

q在一开始要push 0

[蒋昀珀]

    que.push_back(0);
    for(int i=1;i<=n;i++){
        while(que.front()+m<i) que.pop_front();
        ans=max(ans,s[i]-s[que.front()]);
        while(!que.empty()&&s[que.back()]>=s[i]) que.pop_back();
        que.push_back(i);
    }

[蒋昀珀]

回一个