Cod sursa(job #928150)

Utilizator alecsandrualex cuturela alecsandru Data 26 martie 2013 11:53:26
Problema Deque Scor 5
Compilator cpp Status done
Runda Arhiva educationala Marime 0.58 kb
#include<cstdio>
int dq[5000100],k,n,st,dr,v[5000100],s;
void stanga(int i)
{
    if(i-dq[st]==k)
        st++;
}
void dreapta(int i)
{
    while(st<=dr&&v[i]<=v[dq[dr]])
        dr--;
}
int main()
{
    int i;
    freopen("deque.in","r",stdin);
    freopen("deque.out","w",stdout);
    scanf("%d%d",&n,&k);
    for(i=1;i<=n;i++)
    {
        scanf("%d",&v[i]);
    }
    for(i=1;i<=n;i++)
    {
        if(i>k)
            stanga(i);
        dreapta(i);
        dq[++dr]=i;
        if(i>=k)
            s+=v[dq[st]];
    }
    printf("%d",s);
    return 0;
}