Cod sursa(job #1464111)

Utilizator borcanirobertBorcani Robert borcanirobert Data 22 iulie 2015 13:05:38
Problema Deque Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.45 kb
#include <cstdio>
#include <deque>
using namespace std;

const int MAX = 5000010;
const int MAXC = 100010;
//long long a[MAX];
long long N, K;
long long S;
char c[MAXC];
long long p = MAXC - 1;
long long x;
deque< pair<long long, long long> > Q;

void Read();
void Get( long long& x );
void Next();

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

    int i, j;

    Read();
    for ( i = 1; i <= K - 1; i++ )
    {
        Get(x);
        while ( !Q.empty() && x < Q.back().second )
            Q.pop_back();
        Q.push_back( make_pair(i, x) );
    }

    for ( i = K; i <= N; i++ )
    {
        Get(x);
        while ( !Q.empty() && Q.front().first <= i - K )
            Q.pop_front();

        while ( !Q.empty() && x < Q.back().second )
            Q.pop_back();
        Q.push_back( make_pair(i, x) );

        S += Q.front().second;
    }

    printf( "%lld\n", S );

    fclose(stdin);
    fclose(stdout);
    return 0;
}

void Read()
{
    int i;
    Get(N);
    Get(K);
 /*   for ( i = 1; i <= N; i++ )
    {
        scanf( "%lld", &a[i] );
    }   */
}

void Get( long long& x )
{
    bool sgn = 0;
    for ( ; c[p] < '0' || c[p] > '9'; Next() )
        if ( c[p] == '-' )
            sgn = 1;
    for ( x = 0; c[p] >= '0' && c[p] <= '9'; Next() )
        x = x * 10 + ( c[p] - '0' );
    if ( sgn )
        x = -x;
}

void Next()
{
    if ( ++p == MAXC )
    {
        std::fread( c, 1, MAXC, stdin );
        p = 0;
    }
}