Cod sursa(job #2166053)

Utilizator PaulStighiStiegelbauer Paul-Alexandru PaulStighi Data 13 martie 2018 15:17:17
Problema Buline Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.12 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,S,P,L;
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) A[i] = A[i + N] = val;
        else    A[i] = A[i + N] = -val;
    }
}

void Solve()
{
    S = -oo;

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

        if(Best > S)
        {
            S = Best;
            P = Start;
            L = i - Start + 1;
        }
    }
}

void Print()
{
    fout << S << " " << P << " " << L << "\n";
}

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

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