Cod sursa(job #2544038)

Utilizator al3xionescuIonescu Alexandru al3xionescu Data 11 februarie 2020 18:37:16
Problema Deque Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.52 kb
#include <fstream>
#include <deque>
std::ifstream f("deque.in");
std::ofstream g("deque.out");
long long n, k, sol, x;
std::deque< std::pair<long long, int> > d;
int main() {
    f >> n >> k >> x;
    d.push_back({x, 1});
    for (int i = 2; i <= n; i++) {
        f >> x;
        while (!d.empty() && x <= d.back().first)
            d.pop_back();
        d.push_back({x, i});
        if (i - d.front().second >= k)
            d.pop_front();
        if (i >= k)
            sol += d.front().first;
    }

    g << sol;
    return 0;
}