Cod sursa(job #1179206)

Utilizator sorin2kSorin Nutu sorin2k Data 28 aprilie 2014 10:59:15
Problema Deque Scor 25
Compilator cpp Status done
Runda Arhiva educationala Marime 0.71 kb
#include<fstream>
#include<deque>
using namespace std;

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

struct Elem {
    int val;
    int poz;
};

deque<Elem> Q;
int n, a, i, sum, k;

int main() {
    fin >> n >> k;
    for(i = 0; i < n; i++) {
        fin >> a;
        
        while(!Q.empty() && a < Q.back().val) {
            Q.pop_back();
        }
        Elem nou;
        nou.val = a;
        nou.poz = i+1;
        Q.push_back(nou);
        
        if(Q.front().poz <= i+1-k) {
            Q.pop_front();
        }
        if(i + 1 >= k) {
        //    cout << Q.front().val << "\n";
            sum += Q.front().val;
        }
    }
    fout << sum;
    return 0;
}