题解

依旧单调队列

#include<iostream>
#include<queue>
using namespace std;
typedef long long ll;
const int N=5e5+5;
ll n,l,r,a[N],dp[N*2];
int main(){
    cin>>n>>l>>r;
    for(int i=0;i<=n;i++)cin>>a[i];
    deque<int>q;
    dp[0]=a[0];//初始化
    for(int i=1;i<l;i++)dp[i]=-2e9;
    q.push_back(0);
    for(int i=l;i<=n+r;i++){//能跳跃的位置，最左是0+l，最右是n+r
        if(q.size())dp[i]=a[i]+dp[q.front()];//跳跃，dp[q.front()]加上a[i]
        //淘汰
        while(q.size() && dp[q.back()]<dp[i-l+1])q.pop_back();
        //入
        if(i-l+1<=n)q.push_back(i-l+1);
        //老死
        if(q.size() && q.front()==i-r)q.pop_front();
    }
    ll ans=-2e9;
    for(int i=1;i<=r;i++)
        ans=max(ans,dp[n+i]);
    cout<<ans;
    return 0;
}