Cod sursa(job #3347532)

Utilizator Sebastian_Codricisebi codrici Sebastian_Codrici Data 17 martie 2026 09:48:53
Problema Buline Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.24 kb
#include <fstream>

using namespace std;

ifstream cin("buline.in");
ofstream cout("buline.out");

long long v[400005];
long long s[400005];
int deq[400005];

int main() {
    int n;
    cin >> n;
    for (int i=1; i<=n; i++) {
        int va, c;
        cin>>va>>c;
        if (c==0)
            v[i]=-va;
        else
            v[i]=va;
        v[i+n]=v[i];
    }
    for (int i=1; i<=2*n; i++) {
        s[i]=s[i-1]+v[i];
    }
    long long vmax=-2e18;
    int startb=1, lmax=1;
    int f=0, c=0;
    deq[c++]=0;

    for (int i=1; i<2*n; i++) {
        while (f<c&&deq[f]<i-n) {
            f++;
        }
        long long sum=s[i]-s[deq[f]];
        int l=i-deq[f];
        int start=(deq[f]+1>n) ? deq[f] + 1 - n : deq[f] + 1;

        if (sum>vmax) {
            vmax=sum;
            startb=start;
            lmax=l;
        } else if (sum==vmax) {
            if (start<startb) {
                startb=start;
                lmax=l;
            }
            else if (start==startb && l<lmax) {
                lmax=l;
            }
        }
        while (f<c&&s[deq[c-1]]>=s[i]) {
            c--;
        }
        deq[c++]=i;
    }
    cout<<vmax<<" "<<startb<<" "<<lmax<<"\n";
    return 0;
}