Cod sursa(job #300390)

Utilizator bacerandreiBacer Andrei bacerandrei Data 7 aprilie 2009 13:35:11
Problema Deque Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 0.65 kb
#include <stdio.h>
#define max 5000

long n , i , a[max] , deque[max] , front , back , k;
int sum;


int main()
{
  freopen("deque.in" , "r" , stdin);
  freopen("deque.out" , "w" , stdout);
    scanf("%ld%ld" , &n , &k);
      for(i = 1 ; i <= n ; i++)
        scanf("%ld" , &a[i]);
      front = 1; back = 0;
    for(i = 1 ; i <= n ; i++)
     {
        while(front <= back && a[i] < a[deque[back]])
          back--;
        deque[++back] = i;
          if(deque[front] == i-k)
            front++;
        if(i >= k)
          sum += a[deque[front]];
     }
    printf("%d" , sum);
   fclose(stdin);
   fclose(stdout);
 return 0;
}