Cod sursa(job #2458565)

Utilizator uvIanisUrsu Ianis Vlad uvIanis Data 21 septembrie 2019 00:12:46
Problema Deque Scor 25
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.54 kb
#include <iostream>
#include <deque>
#include <fstream>

using namespace std;

int main()
{
    ifstream fin{"deque.in"};
    ofstream fout{"deque.out"};

    int N, K;
    fin >> N >> K;

    int x, s{0};
    deque<pair<int, int>> DQ;

    for(int i = 1; i <= N; ++i)
    {
        fin >> x;

        while(!DQ.empty() && DQ.back().first >= x) DQ.pop_back();

        DQ.push_back(make_pair(x, i));

        if(DQ.front().second + K - 1 < i) DQ.pop_front();

        if(i >= K) s += DQ.front().first;
    }

    fout << s;
}