Cod sursa(job #1771609)

Utilizator RaduMirceaAndreiRadu Mircea Andrei RaduMirceaAndrei Data 5 octombrie 2016 20:07:53
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.23 kb
# include <fstream>
# include <algorithm>
# define DIM 200010
# define INF 2000000000
# define a first.first
# define b first.second
# define c second
using namespace std;
ifstream fin("buline.in");
ofstream fout("buline.out");
pair<pair<int,int>,int> sol[3];
int v[DIM],n,i,stmax,lmax,maxim,val,s,st,ssm;
int main () {
    fin>>n;
    for(i=1;i<=n;i++){
        fin>>v[i]>>val;
        if(1-val)
            v[i]*=-1;
        s+=v[i];
    }
    st=1;
    maxim=-INF;
    for(i=1;i<=n;i++){
        if(ssm<0){
            st=i;
            ssm=v[i];
        }
        else
            ssm+=v[i];
        if(ssm>maxim){
            maxim=ssm;
            stmax=st;
            lmax=i-st+1;
        }
    }
    sol[1].a=-maxim;
    sol[1].b=stmax;
    sol[1].c=lmax;
    st=2;
    maxim=INF;
    ssm=0;
    for(i=2;i<=n-1;i++){
        if(ssm>0){
            st=i;
            ssm=v[i];
        }
        else
            ssm+=v[i];
        if(ssm<maxim){
            maxim=ssm;
            stmax=i+1;
            lmax=i-st+1;
        }
    }
    sol[2].a=-s+maxim;
    sol[2].b=stmax;
    sol[2].c=n-lmax;
    sort(sol+1,sol+3);
    fout<<-sol[1].a<<" "<<sol[1].b<<" "<<sol[1].c<<"\n";
    return 0;
}