Cod sursa(job #354817)

Utilizator MKLOLDragos Ristache MKLOL Data 9 octombrie 2009 17:52:26
Problema Secventa 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.74 kb
#include<stdio.h>

int N,K,v[100000],x,st,dr,max=-10000001,ifin,jfin,dq[100000];

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

    scanf("%d%d",&N,&K);
    for(int i=1;i<=N;++i)
    {
        scanf("%d",&x);
        v[i]=v[i-1]+x;

    }

    st=1;
    dr=0;
    dq[++dr]=0;
    if(K!=N)
    for(int i=0;i+K+1<=N;++i)
    {
        while(st<=dr&&v[dq[dr]]>v[i])
        --dr;
        dq[++dr]=i;
        if(v[i+K+1]-v[dq[st]]>max&&i+K+1<=N)
        {
        max=v[i+K+1]-v[dq[st]];
        ifin=dq[st]+1;
        jfin=i+K+1;
        }
    }
    else
    {
        ifin=1;
        jfin=N;
        max=v[N]-v[0];
    }
    printf("%d %d %d",ifin,jfin,max);

return 0;
}