Cod sursa(job #206819)

Utilizator mihaipoascaPoasca Mihai mihaipoasca Data 9 septembrie 2008 20:36:53
Problema Secventa 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.69 kb
#include<stdio.h>
FILE *fin=fopen("secv2.in","r"),
    *fout=fopen("secv2.out","w");

int N,K,a[50005];
int s[50005],dq[50005];

int main(){

    fscanf(fin,"%d %d",&N,&K);

    for(int i=1;i<=N;i++)
        fscanf(fin,"%d",&a[i]);

    for(int i=1;i<=N;i++)
        s[i]=s[i-1]+a[i];



    int li=1,lf=0;
    int sum,pozi,pozf;
    sum=-500000;
    for(int i=K;i<=N;i++){

       int j=i-K;
       while(lf>=li && s[dq[lf]]>s[j])
            --lf;

        dq[++lf]=j;

        if(s[i]-s[dq[li]] > sum)
            sum=s[i]-s[dq[li]],pozi=dq[li]+1,pozf=i;

    }

    fprintf(fout,"%d %d %d",pozi,pozf,sum);

    fclose(fin);
    fclose(fout);
    return 0;
}