99013 - 跳棋

#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
#include <cstdlib>
#include <cstdio>
using namespace std;
deque < int > Q;
int n, a[1000001], dp[1000001], l, r;

int main()
{
    scanf("%d%d%d", &n, &l, &r);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    memset(dp, -1, sizeof (dp));
    dp[0] = 0;
    for (int i = 1; i <= n; i++)
    {
        while (Q.size() && Q.front() < i - r - 1)
            Q.pop_front();
        if (i - l - 1 >= 0 && dp[i - l - 1] != -1)
        {
            while (Q.size() && dp[Q.back()] > dp[i - l - 1])
                Q.pop_back();
            Q.push_back(i - l - 1);
        }
        if (Q.size()) dp[i] = dp[Q.front()] + a[i];
    }
    printf("%d\n", dp[n]);
    return 0;
}