Cod sursa(job #1054054)

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

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

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

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

    for ( long 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;
}