Cod sursa(job #3345623)

Utilizator G_b_yZamfirache Gabriel G_b_y Data 10 martie 2026 13:37:05
Problema Buline Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.65 kb
#include <bits/stdc++.h>

using namespace std;

int v[200005];
int dp[200005], l[200005];

int main()
{
    freopen("bile.in", "r", stdin);
    freopen("bile.out", "w", stdout);
    int n, sign;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> v[i] >> sign;
        v[i] *= (sign) ? 1 : -1;
    }


    dp[0] = v[0];
    l[0] = 1;
    int current_max = dp[0], max_e = 0, max_l = 1;

    for (int i = 1; i < n; ++i) {
        if (dp[i - 1] > 0) {
            dp[i] = dp[i - 1] + v[i];
            l[i] = l[i - 1] + 1;
        } else {
            dp[i] = v[i];
            l[i] = 1;
        }
        if (current_max < dp[i]) {
            current_max = dp[i];
            max_e = i;
            max_l = l[i];
        } else if (current_max == dp[i]) {
            if (max_e - max_l + 1 > i - l[i] + 1) {
                max_e = i;
                max_l = l[i];
            } else if (max_e - max_l + 1 == i - l[i] + 1) {
                if (max_l > l[i]) {
                    max_e = i;
                    max_l = l[i];
                }
            }
        }
    }

    int sp_val = 0, sp_e = 0, sp_max = 0;
    int start = n - l[n - 1], start_val = dp[n - 1];
    for (int i = 0; i < start; ++i) {
        sp_val += v[i];
        if (sp_val > sp_max) {
            sp_max = sp_val;
            sp_e = i;
        }
    }

    if ( start && (sp_max + start_val > current_max) ) {
        cout << sp_max + start_val << ' ' << start + 1 << ' ' << sp_e + 1 + n - start;
    } else {
        cout << current_max << ' ' << max_e + 2 - max_l << ' ' << max_l;
    }

    return 0;
}

/*
3
1 1
2 1
3 1
*/