Cod sursa(job #3161586)

Utilizator octavian202Caracioni Octavian Luca octavian202 Data 27 octombrie 2023 16:17:06
Problema Buline Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.61 kb
#include <iostream>
#include <fstream>
#include <climits>
#include <deque>

#define ll long long

using namespace std;

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

const ll NMAX = 2e5 + 5;
ll s[2 * NMAX], n, res = INT_MIN, start, lun;
deque<pair<ll, ll> > dq;

int main() {

    fin >> n;
    for (ll i = 1; i <= n; i++) {
        bool alb;
        ll x;
        fin >> x >> alb;
        if (!alb)
            x = -x;
        s[i] = s[i - 1] + x;
        s[i + n] = x;

        ll smin = (!dq.empty() ? dq.front().first : s[1]);
        ll ind = (!dq.empty() ? dq.front().second : 1);
        if (s[i] - smin > res || (s[i] - smin == res && i - ind < lun)) {
            res = s[i] - smin;
            start = ind + 1;
            lun = i - ind;
        }

        while (!dq.empty() && s[i] < dq.back().first) {
            dq.pop_back();
        }
        dq.push_back(make_pair(s[i], i));
    }

    for (ll i = n + 1; i <= 2 * n; i++) {
        s[i] += s[i - 1];

        while (!dq.empty() && dq.front().second < i - n) {
            dq.pop_front();
        }

        ll smin = (!dq.empty() ? dq.front().first : s[1]);
        ll ind = (!dq.empty() ? dq.front().second : 1);
        if (s[i] - smin > res || (s[i] - smin == res && i < start) || (s[i] - smin == res && i - ind < lun)) {
            res = s[i] - smin;
            start = ind + 1;
            lun = i - ind;
        }

        while (!dq.empty() && s[i] < dq.back().first) {
            dq.pop_back();
        }
        dq.push_back(make_pair(s[i], i));
    }

    if (start > n)
        start -= n;

    fout << res << ' ' << start << ' ' << lun;

    return 0;
}