Cod sursa(job #847749)

Utilizator bogdan93Grigorescu Bogdan bogdan93 Data 4 ianuarie 2013 14:07:40
Problema Deque Scor 25
Compilator cpp Status done
Runda Arhiva educationala Marime 0.69 kb
#include <stdio.h>
#include <stdlib.h>

int N , K ;
int deque[2000000] , v[200000];
int s = 0 , p , u ;

int main ()
{
    FILE *fin , *fout ;

    fin = fopen ( "deque.in" , "rt" );
    fout = fopen ( "deque.out" , "wt" );

    fscanf ( fin , "%d %d " , &N , &K );

    p = 1 ;
    u = 0;
    for ( int a , i = 1 ; i <= N ; i++ )
    {
        fscanf ( fin , "%d" , v + i );

        while ( v[i] <= v[deque[u]] && p <= u  ) u--;
        deque[++u] = i ;


        if ( deque[u] - deque[p] == K ) p++;
        if ( i >= K ) s += v[deque[p]];
    }
    //printf ( "suma:%d\n" , s );
    fprintf ( fout , "%d" , s );

    fclose ( fin );
    fclose ( fout );
    return 0;
}