Cod sursa(job #1451959)

Utilizator retrogradLucian Bicsi retrograd Data 19 iunie 2015 09:01:23
Problema Deque Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.61 kb
#include <bits/stdc++.h>

using namespace std;
typedef int var;

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

var V[5000002];

auto cmp = [](var a, var b) { return V[a] > V[b]; };
priority_queue< var, vector<var>, decltype(cmp) > Heap(cmp);

int main() {

    var n, k;
    fin>>n>>k;
    for(var i=1; i<k; i++) {
        fin>>V[i];
        Heap.push(i);
    }

    int64_t sum = 0;
    for(var i=k; i<=n; i++) {
        fin>>V[i];
        Heap.push(i);
        sum += V[Heap.top()];
        while(Heap.top() <= i-k+1)
            Heap.pop();
    }
    fout<<sum;

    return 0;
}