Cod sursa(job #3346560)

Utilizator Gabriel_DaescuDaescu Gabriel Florin Gabriel_Daescu Data 14 martie 2026 11:24:03
Problema Buline Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.05 kb
#include <fstream>
#include <deque>
#define NMAX 200005
using namespace std;

ifstream fin("buline.in");
ofstream fout("buline.out");

int N;
long long v[2*NMAX], sp[2*NMAX];

int main()
{
    fin >> N;

    int x,c;

    for(int i=1;i<=N;i++)
    {
        fin>>x>>c;

        if(c==0) v[i] = -x;
        else v[i] = x;

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

    for(int i=1;i<=2*N;i++)
        sp[i] = sp[i-1] + v[i];

    deque<int> dq;
    dq.push_back(0);

    long long Smax = -9e18;
    int P=1,L=1;

    for(int i=1;i<=2*N;i++)
    {
        while(!dq.empty() && dq.front() < i-N)
            dq.pop_front();

        long long s = sp[i] - sp[dq.front()];

        int start = dq.front()+1;
        int len = i - dq.front();
        int realP = (start-1)%N + 1;

        if(s > Smax)
        {
            Smax = s;
            P = realP;
            L = len;
        }

        while(!dq.empty() && sp[dq.back()] >= sp[i])
            dq.pop_back();

        dq.push_back(i);
    }

    fout<<Smax<<" "<<P<<" "<<L;
}