Cod sursa(job #1248800)

Utilizator darkseekerBoaca Cosmin darkseeker Data 26 octombrie 2014 00:02:51
Problema Deque Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.58 kb
#include <queue>
#include <fstream>
using namespace std;

int main() {
    ifstream fin("deque.in");
    ofstream fout("deque.out");
    int N, K;
    long long sum = 0;
    fin >> N >> K;
    int x;
    deque<pair<int, int> > deck;
    for (int i = 0; i < N; i++) {
        fin >> x;
        while (!deck.empty() && x < deck.back().first)
            deck.pop_back();
        deck.push_back(make_pair(x, i));
        if (i - deck.front().second >= K)
            deck.pop_front();
        if (i >= K - 1)
            sum += deck.front().first;
    }
    fout << sum << endl;
    return 0;
}