Cod sursa(job #632717)

Utilizator yamahaFMI Maria Stoica yamaha Data 12 noiembrie 2011 09:59:38
Problema Deque Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.6 kb
#include<iostream>
#include<fstream>
#include<deque>
using namespace std;

int main ()
{
    ifstream f("deque.in");
    ofstream g("deque.out");
    deque<int> coada, indici;
    int n,k,i,x;
    long long s=0;
    f>>n>>k;
        
    for(i=1;i<=n;i++)
    {
        f>>x;
        while(!coada.empty() && x<=coada.back()) {coada.pop_back(); indici.pop_back();}
        coada.push_back(x); indici.push_back(i);
   
        if(indici.front()<=i-k) {coada.pop_front();indici.pop_front();}
        if(i>=k) {s=s+coada.front();}
    }
    g<<s;
    
    f.close(); g.close();
    return 0;
}