Cod sursa(job #3376341)

Utilizator Gergo123Schradi Gergo Gergo123 Data 17 noiembrie 2026 15:28:08
Problema Buline Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.96 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

bool jobb_jelolt(long long S1, int P1, int L1, long long S2, int P2, int L2) {
    if (S1 != S2) return S1 > S2;
    if (P1 != P2) return P1 < P2;
    return L1 < L2;
}

int main() {
    ifstream fin("buline.in");
    ofstream fout("buline.out");
    int n;
    if (!(fin >> n)) return 0;
    vector<long long> a(n + 1);
    long long teljes_osszeg = 0;
    for (int i = 1; i <= n; i++) {
        long long db;
        int szin;
        fin >> db >> szin;
        a[i] = (szin == 1) ? db : -db;
        teljes_osszeg += a[i];
    }
    long long best_S = a[1];
    int best_P = 1, best_L = 1;
    long long cur_s = a[1];
    int cur_p = 1;
    for (int i = 2; i <= n; i++) {
        if (cur_s < 0) {
            cur_s = a[i];
            cur_p = i;
        }
        else cur_s += a[i];
        int cur_l = i - cur_p + 1;
        if (jobb_jelolt(cur_s, cur_p, cur_l, best_S, best_P, best_L)) {
            best_S = cur_s;
            best_P = cur_p;
            best_L = cur_l;
        }
    }
    if (n >= 3) {
        long long min_mid = a[2];
        int min_l = 2, min_r = 2;
        long long cur_min = a[2];
        int cur_l = 2;
        for (int r = 3; r <= n - 1; r++) {
            if (cur_min > 0) {
                cur_min = a[r];
                cur_l = r;
            }
            else cur_min += a[r];
            if (cur_min < min_mid) {
                min_mid = cur_min;
                min_l = cur_l;
                min_r = r;
            }
        }
        long long wrap_S = teljes_osszeg - min_mid;
        int wrap_P = min_r + 1;
        int wrap_L = n - (min_r - min_l + 1);
        if (jobb_jelolt(wrap_S, wrap_P, wrap_L, best_S, best_P, best_L)) {
            best_S = wrap_S;
            best_P = wrap_P;
            best_L = wrap_L;
        }
    }
    fout << best_S << " " << best_P << " " << best_L << "\n";
    return 0;
}