Pagini recente » Cod sursa (job #243177) | Cod sursa (job #2563474) | Cod sursa (job #3245332) | Cod sursa (job #667687) | Cod sursa (job #383231)
Cod sursa(job #383231)
#include<cstdio>
const int NMAX = 5000005 ;
int k ;
int dq [ NMAX ] , st = 0 , dr = 0 ;
int x [ NMAX ] ;
inline void stanga ( int i )
{
if ( i - dq[st] == k )
++st;
}
void dreapta ( int i )
{
while ( st <= dr && x [ dq[i] ] <= x [ dq[dr] ] )
--dr ;
dq [ ++dr ] = i ;
}
int main ( )
{
freopen ( "deque.in" , "r" , stdin ) ;
freopen ( "deque.out" , "w" , stdout ) ;
int n , i , S =0;
scanf ( "%d%d" , & n , &k ) ;
for ( i = 1 ; i <= n ; ++ i )
scanf ( "%d" , & x[i] ) ;
st=dr=1;
dq[1]=1;
for ( i = 2 ; i <= n ; ++ i )
{
stanga ( i ) ;
dreapta ( i ) ;
if ( i >= k )
S+= x[dq[st]] ;
}
printf ( "%d\n" , S ) ;
return 0 ;
}