Cod sursa(job #1771491)

Utilizator RaduMirceaAndreiRadu Mircea Andrei RaduMirceaAndrei Data 5 octombrie 2016 18:17:19
Problema Buline Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.12 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,mdr,minim,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;
    for(i=1;i<=n;i++){
        if(ssm<0){
            st=i;
            ssm=v[i];
        }
        else
            ssm+=v[i];
        if(ssm==maxs&&st==minst&&i-st+1<minl)
            minl=i-st+1;
        if(ssm==maxs&&st<minst){
            minst=st;
            minl=i-st+1;
        }
        if(ssm>maxs){
            maxs=ssm;
            minst=st;
            minl=i-st+1;
        }
    }
    fout<<maxs<<" "<<minst<<" "<<minl<<"\n";
    return 0;
}