Cod sursa(job #930842)

Utilizator Master011Dragos Martac Master011 Data 27 martie 2013 20:51:20
Problema Deque Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 kb
#include<cstdio>
#define MM 5000100
using namespace std;
FILE *in,*out;

int d[MM],st=1,dr,v[MM],n,k;

inline void stanga(int i){
    if(i-d[st]==k)
        st++;
}

void dreapta (int a){
    while(st<=dr    &&  v[d[dr]]>= a)
        dr--;
}

void citire(){
    fscanf(in,"%d%d",&n,&k);
    for(register int i=1;i<=n;i++)
        fscanf(in,"%d",&v[i]);
}

int main(){
    in=fopen("deque.in","r");
    out=fopen("deque.out","w");

    d[++dr]=1;
    citire();
    long long sum=0;
    for(register int i=2; i<=n ; i++){
        stanga(i);
        dreapta(v[i]);
        d[++dr]=i;
        if(i>=k)
            sum+=v[d[st]];
    }

    fprintf(out,"%lld",sum);
    fclose(in);
    fclose(out);
    return 0;
}