Cod sursa(job #3203172)

Utilizator AnonymousUserBogdan Ionelia AnonymousUser Data 13 februarie 2024 10:49:16
Problema Buline Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.59 kb
#include <iostream>
#include <fstream>

using namespace std;
ifstream fin("buline.in");
ofstream fout("buline.out");
int n, a[200001], sign, length;

int main()
{
    fin>>n;
    for(int i = 1; i <= n; ++i)
    {
        fin>>a[i]>>sign;
        if(sign == 0)
            a[i] *= (-1);
    }
    ///Subsecventa de suma maxima
    int i_start, i_end;
    int current, maxi, imax, jmax;
    current = maxi = a[1];
    i_start = i_end = 1;
    imax = jmax = 1;
    for(int i = 2; i <= n; ++i)
    {
        if(current + a[i] >= a[i])
        {
            current += a[i];
            i_end = i;
            if(current > maxi)
                maxi = current, imax = i_start, jmax = i_end;
            else if(current == maxi)
            {
                if(i_start == imax)
                    jmax = min(jmax, i_end);
                else if(i_start < imax)
                    imax = i_start, jmax = i_end;
            }
        }
        else{
            current = a[i];
            i_start = i_end = i;
            if(current > maxi)
                maxi = current, imax = i_start, jmax = i_end;
        }
    }

    ///Subsecventa de suma minima
    int mini, imin, jmin;
    current = mini = a[1];
    i_start = i_end = 1;
    imin = jmin = 1;
    for(int i = 2; i <= n; ++i)
    {
        if(current + a[i] < a[i])
        {
            current += a[i];
            i_end = i;
            if(current < mini)
                mini = current, imin = i_start, jmin = i_end;
            else if(current == mini)
            {
                if(i_end > jmin)
                    imin = i_start, jmin = i_end;
            }
        }
        else{
            current = a[i];
            i_start = i_end = i;
            if(current < mini)
                mini = current, imin = jmin = i;
        }
    }

    int sum_start = 0, sum_end = 0;
    for(int i = 1; i < imin; ++i)
        sum_start += a[i];
    for(int i = jmin + 1; i <= n; ++i)
        sum_end += a[i];

    length = jmax - imax + 1;
    if(sum_end + sum_start > maxi)
    {
        maxi = sum_end + sum_start;
        imax = jmin+1, jmax = imin - 1;
        length = imin - 1 + n - jmin;
    }
    else if(sum_end + sum_start == maxi)
    {
        if(imax > jmin+1)
            imax = jmin+1, jmax = imin-1, length = imin - 1 + n - jmin;
        else if(imax == jmin+1)
        {
            if(jmax - imax + 1 > n - jmin + imin - 1)
                imax = jmin+1, jmax = imin-1, length = imin - 1 + n - jmin;
        }
    }
    fout<<maxi<<' '<<imax<<' '<<length;
    return 0;
}