Cod sursa(job #1391855)

Utilizator CodrutLemeniCodrut Lemeni CodrutLemeni Data 18 martie 2015 10:54:31
Problema Deque Scor 60
Compilator c Status done
Runda Arhiva educationala Marime 0.6 kb
#include <stdio.h>
#include <stdlib.h>

long long v[5000000];
long long deque[5000000];
long long  p,u,n,k;
long long  i,min;

int main()
{
    freopen("deque.in","r",stdin);
    freopen("deque.out","w",stdout);

    scanf("%d%d",&n,&k);

    for(i=1;i<=n;i++){
        scanf("%lld",&v[i]);
    }
    p=1;
    for(i=1;i<=n;i++){
        while(p<=u && v[i]<v[deque[u]]){
            u--;
        }
        deque[++u]=i;
        if(i-k==deque[p]){
            p++;
        }
       if(i>=k){
            min=min+v[deque[p]];
       }
    }
    printf("%lld",min);
    return 0;
}