Cod sursa(job #2166227)

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

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

int N,S = -oo,P,L;
int A[2 * NMax];

deque <int> DQ;

void Read()
{
    fin>>N;

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

        if(!col)    A[i] *= -1;

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

void Solve()
{
    for(int i = 1 ; i <= 2 * N ; ++i)
        A[i] += A[i - 1];

    DQ.push_back(1);

    for(int i = 2 ; i <= 2 * N ; ++i)
    {
        if(i - DQ.front() > N) DQ.pop_front();

        if(A[i] - A[DQ.front()] > S)
        {
            S = A[i] - A[DQ.front()];
            P = DQ.front() + 1;
            L = i - DQ.front();
        }

        while(!DQ.empty() && A[i] < A[DQ.back()])   DQ.pop_back();

        DQ.push_back(i);
    }
}

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

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

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