Cod sursa(job #633779)

Utilizator irene_mFMI Irina Iancu irene_m Data 14 noiembrie 2011 19:33:14
Problema Deque Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include <cstdio>
#include <deque>

using namespace std;

const int MAX_N = 5000002;

deque < int > Deque, index;
int N, K, val, i;
long long sum;

int main()
{
    freopen( "deque.in", "r", stdin );
    freopen( "deque.out", "w", stdout );

    scanf( "%d %d", &N, &K );
    for( i = 1 ; i <= N; ++i )
    {
        scanf( "%d", &val);
        while( !Deque.empty() && val <= Deque.back() )
        {
            Deque.pop_back();
            index.pop_back();
        }

        Deque.push_back( val );
        index.push_back( i );

        if( index.front() == i - K )
        {
            Deque.pop_front();
            index.pop_front();
        }

        if( i >= K )
            sum += Deque.front();
    }

    printf( "%lld ", sum );
    fclose( stdin );
    fclose( stdout );
    return 0;
}