Pagini recente » Cod sursa (job #2492135) | Cod sursa (job #180291) | Cod sursa (job #1319565) | Cod sursa (job #1984148) | Cod sursa (job #646139)
Cod sursa(job #646139)
#include<cstdio>
using namespace std;
void do_deque( int a[], int n, int k ){
int deque[n], front, back;
int i,j;
front = 0; // front > back => deque empty
back = -1;
int s = 0;
for( i=0; i<n; ++i ){
for( ; back>=front && a[deque[back]] >= a[i]; --back ){ }
deque[++back] = i;
if( deque[front] == i-k ){
++front;
}
if( i >= k-1 ){
// fprintf( stderr, "%d\n", a[deque[front]] );
s += a[deque[front]];
}
}
printf( "%d", s );
}
int main(){
freopen( "deque.in", "r", stdin );
freopen( "deque.out", "w", stdout );
int n,k;
scanf( "%d %d", &n, &k );
int a[n];
for( int i=0; i<n; ++i ){
scanf( "%d", &a[i] );
}
do_deque( a, n, k );
return 0;
}