Cod sursa(job #1182720)

Utilizator Tudordmdaniel marin Tudordm Data 7 mai 2014 11:48:26
Problema Deque Scor 25
Compilator cpp Status done
Runda Arhiva educationala Marime 0.62 kb
#include<stdio.h>

const int Max=5000001;


int d[Max],v[Max],st,dr,k;


void inline stanga(int i){

    if(i-d[st]==k)
        st++;
}

void inline dreapta(int i){

    while(st<=dr&&v[i]<=v[d[dr]])
            dr--;
    d[++dr]=i;
}



int main(){


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

    int a,i,sum=0,n;

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

    for(i=1;i<=n;i++){

            scanf("%d",&v[i]);
            stanga(i);
            dreapta(i);
            if(i>=k){

            sum=sum+v[d[st]];
        }

    }

    printf("%d",sum);

    return 0;
}