Cod sursa(job #646139)

Utilizator tak3rStefan Mirea tak3r Data 10 decembrie 2011 22:31:06
Problema Deque Scor 25
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 kb
#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;
  
}