Cod sursa(job #2166164)

Utilizator PaulStighiStiegelbauer Paul-Alexandru PaulStighi Data 13 martie 2018 15:52:00
Problema Buline Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.58 kb
#include<fstream>
using namespace std;
ifstream fin("buline.in");
ofstream fout("buline.out");

const int NMax = 200005;
const int oo = 1 << 30;

int N,S1,P1,L1,Sum,S2,P2,L2;
int Best,Start;
int A[2 * NMax];

void Read()
{
    fin>>N;

    for(int i = 1 ; i <= N ; ++i)
    {
        int val;    bool col;
        fin >> val >> col;

        if(!col)    val *= -1;

        A[i] = A[N + i] = val;

        Sum += A[i];
    }
}

void Solve()
{
    Best = 0;   Start = 1;

    for(int i = 1 ; i <= 2 * N ; ++i)
    {
        if(A[i] + Best < A[i])
        {
            if(i > N)   break;
            Best = A[i];
            Start = i;
        }
        else    Best += A[i];

        if(S1 < Best && i - Start + 1 <= N)
        {
            S1 = Best;
            P1 = Start;
            L1 = i - Start + 1;
        }
    }

    Best = 0;   Start = 1;

    for(int i = 1 ; i <= 2 * N ; ++i)
    {
        if(A[i] + Best > A[i])
        {
            if(i > N)   break;
            Best = A[i];
            Start = i;
        }
        else    Best += A[i];

        if(S2 > Best && i - Start + 1 <= N)
        {
            S2 = Best;
            P2 = Start;
            L2 = i - Start + 1;
        }
    }

    P2 += L2 = 1;

    L2 = N - L2;

    if(Sum - S2 > S2 && L2 != 0)
    {
        S1 = Sum - S2;
        P1 = P2;
        L1 = L2;
    }
}

void Print()
{
    fout << S1 << " " << P1 << " " << L1 << "\n";
}

int main()
{
    Read();
    Solve();
    Print();

    fin.close();
    fout.close();
    return 0;
}