Mai intai trebuie sa te autentifici.
Cod sursa(job #847750)
Utilizator | Data | 4 ianuarie 2013 14:08:57 | |
---|---|---|---|
Problema | Deque | Scor | 25 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.71 kb |
#include <stdio.h>
#include <stdlib.h>
#define nmax 5000000
int N , K ;
int deque[nmax] , v[nmax];
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;
}