常规题解

#include <iostream>
#include <deque>
#define int long long
using namespace std;
const int maxn = 200005;
const int INF = 1e18;
int n,l,r,a[maxn];
int dp[maxn];
deque<int> q;
signed main(){
    cin >> n >> l >> r;
    for(int i = 0;i <= n;i++)cin >> a[i];
    for(int i = 1;i <= n;i++)dp[i] = -INF;
    for(int i = 1;i <= n;i++){
        int x = i - l;
        while(!q.empty() && q.front() < i - r){
            q.pop_front();
        }
        if(x >= 0 && dp[x] != -INF){
            while(!q.empty() && dp[q.back()] <= dp[x]){
                q.pop_back();
            }
            q.push_back(x);
        }
        if(!q.empty()){
            dp[i] = dp[q.front()] + a[i];
        }
    }
    int ans = -INF;
    for(int i = n - r + 1;i <= n;i++){
        ans = max(ans,dp[i]);
    }
    cout << ans;
}