Cod sursa(job #2610985)

Utilizator Harsa_AndreiHarsa Andrei Harsa_Andrei Data 6 mai 2020 00:11:14
Problema Deque Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.63 kb
#include <fstream>
#include <deque>

using namespace std;

ifstream fin("deque.in");
ofstream fout("deque.out");

deque<pair<int,int>> dq;

int main()
{
    int n, k, x;
    long long res = 0;
    fin >> n >> k >> x;
    dq.push_back(make_pair(x, 1));
    for(int i = 2; i <= n; i++)
    {
        fin >> x;
        while(!dq.empty() && dq.back().first > x)
            dq.pop_back();
        dq.push_back(make_pair(x, i));
        if(i >= k)
        {
            if(dq.front().second <= i - k)
                dq.pop_front();
            res += dq.front().first;
        }
    }
    fout << res;
    return 0;
}