Cod sursa(job #3371332)

Utilizator Floroiu_MariusFloroiu Marius Cristian Floroiu_Marius Data 29 octombrie 2026 19:34:05
Problema Buline Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("buline.in");
ofstream fout("buline.out");
int n;
int v[200003];
long long sp[400003];
deque<int> dq;
int Max,st,l;
int main()
{
    fin>>n;
    for (int i=1; i<=n; i++)
    {
        int x,t;
        fin>>x>>t;
        v[i]=x;
        if (t==0) v[i]=-x;
    }
    dq.push_back(0);
    for (int i=1; i<=2*n; i++)
    {
        int val=0;
        if (i<=n) val=v[i];
        else val=v[i-n];
        sp[i]=sp[i-1]+val;
        while (!dq.empty() && sp[i]<sp[dq.back()]) dq.pop_back();
        if (!dq.empty())
        {
            long long sum=sp[i]-sp[dq.front()];
            if (sum>Max)
            {
                Max=sum;
                st=dq.front()+1;
                l=i-st+1;
            }
        }
        dq.push_back(i);
        if (dq.front()==i-n) dq.pop_front();
    }
    fout<<Max<<" "<<st<<" "<<l;
    return 0;
}