Cod sursa(job #994993)

Utilizator TarabanDragosTaraban Dragos-Petru TarabanDragos Data 6 septembrie 2013 22:16:22
Problema Buline Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.4 kb
#include<cstdio>
#include<climits>
int n,v[200001],x[200001],y[200001],s,in,d,smax=INT_MIN,imax,dmax,i,j,a,c,smin=INT_MAX,dmin,imin,st;
FILE *f,*g;
int main(){
    f=fopen("buline.in","r");
    g=fopen("buline.out","w");
    fscanf(f,"%d",&n);
    imax=0;
    dmax=0;
    s=0;
    in=1;
    d=0;
    for(i=1;i<=n;i++){
        fscanf(f,"%d%d",&a,&c);
        if(c==1)
            v[i]=a;
        else
            v[i]=-a;
        st+=v[i];
         if(s+v[i]>=v[i]){
            d++;
            s+=v[i];
            if(s>smax){
                smax=s;
                dmax=d;
                imax=in;
            }
        }
        else{
            s=v[i];
            in=i;
            d=1;
        }
    }
    d=0;
    in=1;
    dmin=0;
    imin=0;
    s=0;
    for(i=1;i<=n;i++){
        if(s+v[i]<=v[i]){
            d++;
            s+=v[i];
            if(s<smin){
                smin=s;
                dmin=d;
                imin=in;
            }

        }
        else{
            s=v[i];
            if(s<smin){
                smin=s;
                dmin=d;
                imin=in;
            }
            in=i;
            d=1;
        }
    }
    s=st-smin;
    if(s>smax){
        smax=s;
        imax=imin+dmin+1;
        dmax=n-dmin+1;
    }
    fprintf(g,"%d %d %d",smax,imax,dmax);
    fclose(f);
    fclose(g);
    return 0;
}