题解

单调队列可以快速求区间最值

#include <iostream>
#include <deque>
using namespace std;
typedef long long ll;
const ll N = 2e5 + 5;
ll a[N];
ll dp[2*N];
int main(){
    ll n, l, r;
    cin >> n >> l >> r;
    for(int i=0; i<=n; i++){
        cin >> a[i];
    }
    dp[0] = a[0];
    deque<int>q;
    for(int i=1;i<l;i++)dp[i]=-2e9;
    q.push_back(0);
    for(int i=l;i<=n+r;i++){
        if(q.size())dp[i]=a[i]+dp[q.front()];
        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;
}