Cod sursa(job #686592)

Utilizator bursuc13bogdan bursuc13 Data 21 februarie 2012 18:54:05
Problema Deque Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.57 kb
#include <fstream>
#include <deque>
using namespace std;

int n,k;
deque< pair<int, int> > d;
long long s;

int main()
{
    ifstream f("deque.in");
    ofstream g("deque.out");
    
    int i,v;
    f>>n>>k;
    for(i=0; i<n ; ++i )
    {
           f>>v;
           
           while(!d.empty() && d.back().first > v)
           d.pop_back();
           
           d.push_back(make_pair(v, i));
           if(d.front().second + k == i)
           d.pop_front();
           
           s+=i<k-1 ? 0 : d.front().first;
    }
    g<<s;
    return 0;
}