Cod sursa(job #1561810)

Utilizator PopoviciRobertPopovici Robert PopoviciRobert Data 4 ianuarie 2016 16:14:12
Problema Secventa 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <cstdio>
#define MAXN 50000
#define INF 1000000000
int d[MAXN+1],s[MAXN+1],poz[MAXN+1];
int main(){
    FILE*fi,*fout;
    int k,i,n,max,st,dr;
    fi=fopen("secv2.in" ,"r");
    fout=fopen("secv2.out" ,"w");
    fscanf(fi,"%d%d" ,&n,&k);
    for(i=1;i<=n;i++){
        fscanf(fi,"%d" ,&s[i]);
        s[i]+=s[i-1];
    }
    max=d[k-1]=-INF;
    for(i=k;i<=n;i++){
        if(s[i]-s[i-k]>d[i-1]+s[i]-s[i-1]){
            d[i]=s[i]-s[i-k];
            poz[i]=i-k+1;
            if(d[i]>max){
                max=d[i];
                st=i-k+1;
                dr=i;
            }
        }
        else{
            d[i]=d[i-1]+s[i]-s[i-1];
            poz[i]=poz[i-1];
            if(d[i]>max){
                max=d[i];
                st=poz[i];
                dr=i;
            }
        }
    }
    fprintf(fout,"%d %d %d" ,st,dr,max);
    fclose(fi);
    fclose(fout);
    return 0;
}