Cod sursa(job #2624782)

Utilizator matei123Biciusca Matei matei123 Data 5 iunie 2020 12:36:50
Problema Buline Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.9 kb
#include<bits/stdc++.h>
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);
    }
}
int main()
{   Read();
    Solve();
    fout << S << " " << P << " " << L;
    return 0;
}