Cod sursa(job #1495533)

Utilizator theodor.moroianuTheodor Moroianu theodor.moroianu Data 3 octombrie 2015 11:12:57
Problema Deque Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 0.53 kb
#include <fstream>
#include <deque>

using namespace std;

struct a{
    int v, poz;
};

deque <a> d;

int n, k, q;
long long r = 0;

int main(){
    ifstream in("deque.in");
    ofstream out("deque.out");
    in >> n >> k;
    for (int i = 0; i < n; i++){
        in >> q;
        while(!d.empty() && q <= d.front().v)
            d.pop_front();
        d.push_front((a){q, i});
        if (d.front().poz - d.back().poz >= k)
            d.pop_back();
        if(i + 1 >= k)
            r += d.back().v;
    }
    out << r;


    return 0;
}