Cod sursa(job #1054053)

Utilizator morlockRadu Tatomir morlock Data 13 decembrie 2013 12:27:35
Problema Deque Scor 25
Compilator cpp Status done
Runda Arhiva educationala Marime 0.61 kb
#include <iostream>
#include <fstream>
#include <deque>
#include <utility>
#define nmax 500005
using namespace std;

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

long N, x, K, S=0;
deque < pair<long, long> > deq;

int main()
{
    in >> N >> K;

    for ( long i=0; i<N; ++i )
    {
        in >> x;
        while ( !deq.empty() && deq.back().first >= x )
            deq.pop_back();

        deq.push_back( make_pair(x, i) );

        if ( deq.front().second <= i-K )
            deq.pop_front();

        if (i >= K-1)
            S += deq.front().first;
    }

    out << S;
}