Cod sursa(job #916744)

Utilizator lehman97Dimulescu David lehman97 Data 16 martie 2013 20:44:03
Problema Secventa 2 Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.82 kb
#include <iostream>
#include <stdio.h>

using namespace std;

FILE *f=fopen("secv2.in","r");
FILE *g=fopen("secv2.out","w");

struct vec
{
    int x,y;

}best[50005],mn;

int n,k,mx,sol,nr,i,a,sum[50005],sf,in;

int main()
{
    fscanf(f,"%d%d",&n,&k);
    nr=0;
    sum[0]=0;
    for(i=1;i<=n;i++)
    {
        fscanf(f,"%d",&a);
        sum[i]=sum[i-1]+a;
    }
    mn.x=sum[1];
    mn.y=1;
    best[0].x=0;
    best[0].y=0;
    best[1]=mn;
    for(i=2;i<=n;i++)
    {
        if(sum[i]<mn.x){mn.x=sum[i];mn.y=i;}
        best[i]=mn;
    }
    for(i=k;i<=n;i++)
    {
        if(i==k){mx=sum[i]-best[i-k].x;sf=i;in=best[i-k].y+1;} else
        if(sum[i]-best[i-k].x>mx){mx=sum[i]-best[i-k].x;sf=i;in=best[i-k].y+1;}

    }


    fprintf(g,"%d %d %d",in,sf,mx);
    fclose(g);
    return 0;
}