Cod sursa(job #354813)

Utilizator MKLOLDragos Ristache MKLOL Data 9 octombrie 2009 17:36:31
Problema Secventa 2 Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.61 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;
    for(int i=1;i<=N;++i)
    {
        while(st<=dr&&v[dq[dr]]>v[i])
        --dr;
        dq[++dr]=i;
        if(v[i+K]-v[dq[st]]>max&&K+i<=N)
        {
        max=v[i+K]-v[dq[st]];
        ifin=dq[st]+1;
        jfin=i+K;
        }
    }
    printf("%d %d %d",ifin,jfin,max);

return 0;
}