Cod sursa(job #2406158)

Utilizator IulianOleniucIulian Oleniuc IulianOleniuc Data 15 aprilie 2019 14:06:39
Problema Deque Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.68 kb
#include <deque>
#include <utility>
#include <fstream>

using std::pair;
using std::deque;
using std::make_pair;

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

int main() {
    int n, k;
    fin >> n >> k;

    int64_t sol = 0;
    deque<pair<int, int>> dq;

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

        if (i >= k - 1)
            sol += dq.front().first;
    }
    fout << sol << '\n';

    fout.close();
    return 0;
}