Cod sursa(job #1759532)

Utilizator pfaaiFlorinel Salamiut pfaai Data 19 septembrie 2016 14:30:44
Problema Deque Scor 25
Compilator cpp Status done
Runda Arhiva educationala Marime 0.57 kb
#include <fstream>
#include <deque>

using namespace std;

int n, k;

//position and value
deque<pair<int, int>> d;

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

    in >> n >> k;

    int sol = 0, value;

    for (int i = 0; i < n; i++) {
        in >> value;

        while (!d.empty() && value < d.back().second)
            d.pop_back();

        d.push_back(make_pair(i, value));

        if (i - d.front().first == k)
            d.pop_front();

        if (i >= k - 1)
            sol += d.front().second;
    }

    out << sol;
    return 0;
}