Cod sursa(job #3283376)

Utilizator deerMohanu Dominic deer Data 9 martie 2025 13:32:22
Problema Buline Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.8 kb
#include <bits/stdc++.h>

#define int long long
#define fi first
#define se second

#define sz(a) int((a).size())
#define all(a) (a).begin(), (a).end()

#define lsb(x) (x & (-x))
#define vi vector<int>
#define YES { cout << "YES" << endl; return; }
#define NO { cout << "NO" << endl; return; }

using ll = long long;
using pii = std::pair<int, int>;
const int NMAX = 2e5;
using namespace std;
ifstream fin("buline.in");
ofstream fout("buline.out");
int v[NMAX + 5], pre[2 * NMAX + 5], n;
signed main() {
    fin >> n;
    for (int i = 0, x, clr; i < n; ++i) {
        fin >> x >> clr;
        v[i] = (clr == 0 ? -x : x);
    }
    int best_sum = LLONG_MIN, sum = 0;
    int start = 0, best_start = -1, best_length = 0;
    for (int i = 0; i < n; ++i) {
        if (sum <= 0) {
            sum = v[i];
            start = i;
        } else
            sum += v[i];
        if (sum > best_sum || (sum == best_sum && (start < best_start || (start == best_start && (i - start + 1) < best_length)))) {
            best_sum = sum;
            best_start = start;
            best_length = i - start + 1;
        }
    }
    for (int i = 0; i < 2 * n; ++i)
        pre[i] = v[i % n];
    sum = 0, start = 0;
    for (int i = 0; i < 2 * n; ++i) {
        if (i - start == n) {
            sum -= pre[start];
            start++;
        }
        if (sum <= 0) {
            sum = pre[i];
            start = i;
        } else {
            sum += pre[i];
        }
        
        if (i - start + 1 <= n && (sum > best_sum || (sum == best_sum && (start % n < best_start || (start % n == best_start && (i - start + 1) < best_length))))) {
            best_sum = sum;
            best_start = start % n;
            best_length = i - start + 1;
        }
    }
    fout << best_sum << " " << best_start + 1 << " " << best_length << "\n";
    return 0;
}