Cod sursa(job #1979670)

Utilizator MihaelaCismaruMihaela Cismaru MihaelaCismaru Data 11 mai 2017 07:58:14
Problema Buline Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.88 kb
#include<fstream>
using namespace std;
ifstream in("buline.in");
ofstream out("buline.out");
int v[200001],lmin[200001],lmax[200001],dmax[200001],dmin[200001],pozmax[200001],pozmin[200001];
int lunmax,lunmin,maxim,minim,alfamin,alfamax,ok,n,i,x;
long long s;
int main(){
    in >> n;
    for( i = 1; i <= n; i ++ ){
        in >> v[i];
        in >> x;
        if( x == 0 ){
            v[i] *= -1;
        }
        s+=v[i];
    }
    for( i = 1; i <= n; i ++ ){
        if( dmax[i-1] <= 0 || i == 1 ){
            dmax[i] = v[i];
            pozmax[i] = i;
            lmax[i] = 1;
        }
        else{
            dmax[i] = dmax[i-1]+v[i];
            pozmax[i] = pozmax[i-1];
            lmax[i]=lmax[i-1]+1;
        }

        if( ok == 0 ){
            maxim = dmax[i];
            alfamax = pozmax[i];
            lunmax = lmax[i];
            ok = 1;
        }
        if( dmax[i] > maxim ){
            maxim = dmax[i];
            alfamax = pozmax[i];
            lunmax = lmax[i];
        }

    }
    ok = 0;
    for( i = 1; i <= n; i ++ ){
        if( dmin[i-1] >= 0 || i == 1 ){
            dmin[i] = v[i];
            pozmin[i] = i;
            lmin[i] = 1;
        }
        else{
            dmin[i] = dmin[i-1]+v[i];
            pozmin[i] = pozmin[i-1];
            lmin[i]++;
        }
        if( ok == 0 ){
            minim = dmin[i];
            alfamin = pozmin[i];
            lunmin = lmin[i];
            ok = 1;
        }
        if( dmin[i] < minim ){
            minim = dmin[i];
            alfamin = pozmin[i];
            lunmin = lmin[i];
        }

    }
    if( maxim >= s - minim ){
        out <<maxim<<" "<<alfamax<<" "<<lunmax;
    }
    else{
        if( alfamin + 1 != n ){
            alfamin = alfamin % n +1;
        }
        out<<s-minim<<" "<<alfamin <<" "<<n-lunmin;
    }


    return 0;
}