Cod sursa(job #1464105)

Utilizator borcanirobertBorcani Robert borcanirobert Data 22 iulie 2015 12:48:06
Problema Deque Scor 25
Compilator cpp Status done
Runda Arhiva educationala Marime 1.3 kb
#include <cstdio>
#include <deque>
using namespace std;

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

void Read();
void Get( int& 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++ )
    {
        while ( !Q.empty() && a[i] < a[Q.back()] )
            Q.pop_back();
        Q.push_back(i);
    }

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

        while ( !Q.empty() && a[i] < a[Q.back()] )
            Q.pop_back();
        Q.push_back(i);

        S += a[Q.front()];
    }

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

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

void Read()
{
    int i;
    Get(N);
    Get(K);
    for ( i = 1; i <= N; i++ )
    {
        Get(x);
        a[i] = x;
    }
}

void Get( int& 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;
    }
}