Cod sursa(job #1647754)

Utilizator AnaRaduAna-Maria Radu AnaRadu Data 10 martie 2016 21:56:49
Problema Secventa 2 Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <stdio.h>
#define lim 50005
int s[lim],best[lim],lg[lim];
int max(int a,int b){
    if(a>b)
        return a;
    else
        return b;
}
int main(){
    FILE *fin,*fout;
    fin=fopen("secv2.in","r");
    fout=fopen("secv2.out","w");
    int i,n,k,x,st,dr,rasp=-2000000000,sum,lg;
    fscanf(fin,"%d%d",&n,&k);
    for(i=1;i<=n;i++){
        fscanf(fin,"%d",&x);
        s[i]=s[i-1]+x;
        best[i]=max(x,best[i-1]+x);
    }
    for(i=k;i<=n;i++)
        if(s[i]-s[i-k]+best[i-k]>rasp){
            rasp=s[i]-s[i-k]+best[i-k];
            dr=i;
            st=i-k;
        }
    sum=-2000000000;
    lg=0;
    for(i=1;i<=st;i++){
        if(sum+s[i]-s[i-1]>s[i]-s[i-1]){
            lg++;
            sum=sum+s[i]-s[i-1];
        }
        else{
            sum=s[i]-s[i-1];
            lg=1;
        }
    }
    st=st-lg+1;
    fprintf(fout,"%d %d %d",st,dr,rasp);
    fclose(fin);
    fclose(fout);
    return 0;
}