Cod sursa(job #811703)

Utilizator gabipurcaruGabi Purcaru gabipurcaru Data 12 noiembrie 2012 20:44:49
Problema Deque Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.53 kb
#include <fstream>
#include <utility>
#include <queue>
using namespace std;

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

int a, n, i, j, k;
long long s;
deque<pair<int,int> > m;

int main() {
    in>>n>>k;
    for(i=1; i<=n; i++) {
        in>>a;
        while(!m.empty() && m.back().first >= a) {
            m.pop_back();
        }
        m.push_back(make_pair(a, i));
        while(m.front().second <= i-k)
            m.pop_front();
        if(i >= k) {
            s += m.front().first;
        }
    }
    out<<s;
    return 0;
}