Cod sursa(job #281515)

Utilizator ViksenVictor-Nicolae Savu Viksen Data 15 martie 2009 10:53:46
Problema Deque Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.56 kb
#include<fstream>
#include<utility>
#include<queue>
using namespace std;

deque< pair<int,int> > Q;

int main() {

    int n,k;
    long long s=0;
    ifstream fin; fin.open("deque.in");
    fin>>n>>k;
    for(int i=0,x ; i<n ; i++) {
        fin>>x;
        while(!Q.empty() && x<Q.back().first) Q.pop_back();
        Q.push_back(make_pair(x,i));
        while(!Q.empty() && i-Q.front().second >= k) Q.pop_front();
        if(i>=k-1) s+=Q.front().first;
    }

    fin.close();
    ofstream fout; fout.open("deque.out");
    fout<<s<<'\n';
    fout.close();

    return 0;
}