Cod sursa(job #2905708)

Utilizator UengineDavid Enachescu Uengine Data 23 mai 2022 10:29:53
Problema Deque Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.73 kb
#include <fstream>
#include <deque>

using namespace std;

ifstream cin("sum2.in");
ofstream cout("sum2.out");

const int N = 1e5;

int sum[N + 5];
deque <int> d;

int main()
{

    int n, l, u, rez = -2e9;
    cin >> n >> l >> u;
    for (int i = 1; i <= n; i++)
    {
        int x;
        cin >> x;
        sum[i] = sum[i-1] + x;
        if (i < l)
        {
            continue;
        }
        if (!d.empty() && d.front() == i - u - 1)
        {
            d.pop_front();
        }
        while (!d.empty() && sum[d.back()] >= sum[i-l])
        {
            d.pop_back();
        }
        d.push_back(i-l);
        rez = max(rez, sum[i] - sum[d.front()]);
    }
    cout << rez;
    return 0;
}