Cod sursa(job #3166152)

Utilizator AdrianRosuRosu Adrian Andrei AdrianRosu Data 7 noiembrie 2023 19:41:47
Problema Buline Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.19 kb
#include <bits/stdc++.h>
#define DIM 400001

using namespace std;

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

int v[DIM], sp[DIM];

deque <int> d;

int n, i, sign, Max = -1e9, start, len;

int main(){

    fin >> n;

    for(i=1;i<=n;i++){

        fin >> v[i] >> sign;

        v[i] *= (sign == 1) ? 1 : -1;

    }

    for(i=n+1;i<=2 * n;i++)
        v[i] = v[i - n];

    n *= 2;

    // suma maxima cu lungime maxim n

    for(i=1;i<=n;i++)
        sp[i] = sp[i - 1] + v[i];

    d.push_back(0);

    for(i=1;i<=n;i++){

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

        d.push_back(i);

        if(i > n / 2){

            while(!d.empty() && i - d.front() + 1 > n / 2)
                d.pop_front();

        }

        if(Max < sp[i] - sp[d.front()]){

            Max = sp[i] - sp[d.front()];

            start = d.front() + 1;

            len = i - d.front();

        }

        else if(Max == sp[i] - sp[d.front()] && i - d.front() < len){

            start = d.front() + 1;

            len = i - d.front();

        }

    }

    fout << Max << " " << start << " " << len;


}