Cod sursa(job #2547705)

Utilizator Bogdan_BuzatuBuzatu Bogdan Mihai Bogdan_Buzatu Data 15 februarie 2020 16:43:56
Problema Buline Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.44 kb
#include <fstream>
using namespace std;

ifstream fin("buline.in");
ofstream fout("buline.out");

int n, cl, suma,i;
int maxim, maxpoz, maxlung;
int minim, minpoz, minlung;
int v[200005],s[200005], l[200005];

int main()
{

    fin>>n;
    for(i=1;i<=n;i++){
        fin>>v[i]>>cl;
        if(cl==0){
            v[i]=-v[i];
        }
        suma+=v[i];
    }

    s[1] = v[1];
    l[1] = 1;

    for(i=2;i<=n;i++){
        if(s[i-1]+v[i]>=v[i]){
            s[i]=s[i-1]+v[i];
            l[i] = l[i-1]+1;
        }
        else{
            s[i]=v[i];
            l[i]=1;
        }
    }


    maxim = s[1];
    maxpoz = 1;
    maxlung = 1;
    for(i=2;i<=n;i++){
        if(maxim<s[i]){
            maxim =s[i];
            maxpoz =i-l[i]+1;
            maxlung=l[i];
        }
    }

    s[1]=v[1];
    l[1]=1;

    for(i=2;i<=n;i++){
        if(s[i-1]+v[i]<=v[i]){
            s[i]=s[i-1]+v[i];
            l[i] = l[i-1]+1;
        }
        else{
            s[i]=v[i];
            l[i]=1;
        }
    }

    minim=s[1];
    minpoz = 1;
    minlung = 1;
     for(i=2;i<=n;i++){
        if(minim>s[i]){
            minim =s[i];
            minpoz =i-l[i]+1;
            minlung=l[i];
        }
    }

    if(maxim>suma-minim){
        fout<<maxim<<" "<<maxpoz<<" "<<maxlung;
    }

    else{
        fout<<suma-minim<<" "<<minpoz + minlung<<" "<<n-minlung;
    }


    return 0;
}