Cod sursa(job #2887524)

Utilizator mihairazvan03Dana Mihai mihairazvan03 Data 9 aprilie 2022 19:16:32
Problema Deque Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.06 kb
#include <iostream>
#include <fstream>

using namespace std;

ifstream in("grader_test7.in");
ofstream out("deque.out");

long long n, k, i, suma, x, dFront, dBack, dSize;
pair<long long, long long> deq[500010];

int main()
{
    in >> n >> k;
    dFront = n - 2;
    dBack = n - 1;
    dSize = 0;


    for(i = 1; i <= k; i++)
    {
        in>>x;

        while(dSize > 0 && deq[dBack].first >= x)
        {
            dBack++;
            dSize--;
        }

        dBack--;
        dSize++;
        deq[dBack] = make_pair(x, i);
    }

    suma = deq[dFront].first;

    for(i = k + 1; i <= n; i++)
    {
        in>>x;
        while(dSize > 0 && i - deq[dFront].second >= k)
        {
            dFront--;
            dSize--;
        }

        while(dSize > 0 && deq[dBack].first >= x)
            {
                dBack++;
                dSize--;
            }

        dBack--;
        dSize++;
        deq[dBack] = make_pair(x, i);

        suma += deq[dFront].first;
    }

    out<<suma;

    return 0;
}