Cod sursa(job #3261487)

Utilizator BledeaAlexBledea Alexandru BledeaAlex Data 6 decembrie 2024 12:48:07
Problema Buline Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.89 kb
#include <bits/stdc++.h>

using namespace std;

const int N_MAX = 2e5 + 1;
int N, sum;
int v[N_MAX];

tuple<int, int, int> ans;

void SetInput(string name)
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    (void)!freopen((name + ".in").c_str(), "r", stdin);
    (void)!freopen((name + ".out").c_str(), "w", stdout);
}

void ReadArray()
{
    cin >> N;

    sum = 0;
    for(int i = 1, t; i <= N; i++)
    {
        cin >> v[i] >> t;
        if(t == 0)
            v[i] = -v[i];

        sum += v[i];
    }

}

void CompareToAns(tuple<int, int, int>& t)
{
    if(get<0>(ans) < get<0>(t))
        ans = t;
    else if(get<0>(ans) == get<0>(t))
    {
        if(get<1>(ans) > get<1>(t))
            ans = t;
        else if(get<1>(ans) == get<1>(t) && get<2>(ans) > get<2>(t))
            ans = t;
    }
}

void Solve()
{
    pair<int, int> ssMin, ssMax;
    tuple<int, int, int> temp;

    ssMin = ssMax = make_pair(v[1], 1);

    ans = make_tuple(ssMax.first, 1, 1);
    temp = make_tuple(sum - ssMin.first, 2, N-1);
    CompareToAns(temp);

    for(int i = 2; i <= N; i++)
    {
        /// Find ssMax

        if(ssMax.first < 0)
            ssMax = make_pair(v[i], i);
        else
            ssMax.first += v[i];

        temp = make_tuple(ssMax.first, ssMax.second, i - ssMax.second + 1);
        CompareToAns(temp);

        /// Find ssMin

        if(ssMin.first > 0)
            ssMin = make_pair(v[i], i);
        else
            ssMin.first += v[i];

        temp = make_tuple(sum - ssMin.first, i + 1, N - (i - ssMin.second + 1)); /// Can have N + 1 (for i = N) since it is at most worse than sum of first N nums
        CompareToAns(temp);
    }

    cout << get<0>(ans) << ' ' << get<1>(ans) << ' ' << get<2>(ans) << '\n';
}

int main()
{
    SetInput("buline");

    ReadArray();
    Solve();

    return 0;
}