Cod sursa(job #1771505)

Utilizator RaduMirceaAndreiRadu Mircea Andrei RaduMirceaAndrei Data 5 octombrie 2016 18:40:05
Problema Buline Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.23 kb
# include <fstream>
# define DIM 200010
using namespace std;
ifstream fin("buline.in");
ofstream fout("buline.out");
int v[DIM],n,i,val,s,ssm,st,dr,mst,maxst,maxl,mdr,minim,maxim,maxs,minst,minl;
int main () {
    fin>>n;
    for(i=1;i<=n;i++){
        fin>>v[i]>>val;
        if(1-val)
            v[i]=-v[i];
        s+=v[i];
    }
    st=2;
    for(i=2;i<=n-1;i++){
        if(ssm>0){
            st=i;
            ssm=v[i];
        }
        else
            ssm+=v[i];
        if(ssm<minim){
            minim=ssm;
            mst=st;
            mdr=i;
        }
    }
    maxs=s-minim;
    minst=st+1;
    minl=n-mdr+mst-1;
    ssm=0;
    st=1;
    maxim=-2000000000;
    for(i=1;i<=n;i++){
        if(ssm<0){
            st=i;
            ssm=v[i];
        }
        else
            ssm+=v[i];
        if(ssm>maxim){
            maxim=ssm;
            maxst=st;
            maxl=i-st+1;
        }
    }
    if(maxs==maxim&&minst==maxst&&maxl<minl)
        minl=maxl;
    if(maxs==maxim&&maxst<minst){
        minst=maxst;
        minl=maxl;
    }
    if(maxim>maxs){
        maxs=maxim;
        minst=maxst;
        minl=maxl;
    }
    fout<<maxs<<" "<<minst<<" "<<minl<<"\n";
    return 0;
}