Cod sursa(job #3361291)

Utilizator adimiclaus15Miclaus Adrian Stefan adimiclaus15 Data 22 iulie 2026 20:29:16
Problema Buline Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.99 kb
#include <bits/stdc++.h>
using namespace std;

int n, m;
int a[200001];
int dp1[200001], dp2[200001];

int main() {
    ifstream cin("buline.in");
    ofstream cout("buline.out");
    //Subsecventa de suma maxima pe sirul liniar
    //Total - subsecventa de suma minima pe sirul liniar
    cin >> n;
    for(int i = 1; i <= n; i++) {
        int x, y;
        cin >> x >> y;
        if(y == 0) {
            a[i] = -x;
        } else {
            a[i] = x;
        }
    }
    //Cazul 1. Subsecventa de suma maxima pe sirul liniar
    dp1[1] = a[1];
    for(int i = 2; i <= n; i++) {
        dp1[i] = max(dp1[i - 1] + a[i], a[i]);
    }
    int s1 = -10000;
    int pf1 = 0;
    for(int i = 1; i <= n; i++) {
        if(dp1[i] > s1) {
            s1 = dp1[i];
            pf1 = i;
        }
    }
    int s3 = s1;
    int ps1 = 0;
    for(int i = pf1; i >= 1; i--) {
        s3 -= a[i];
        if(s3 == 0) {
            ps1 = i;
            break;
        }
    }
    //Cazul 2. Total - subsecventa de suma minima pe sirul liniar
    dp2[1] = a[1];
    for(int i = 2; i <= n; i++) {
        dp2[i] = min(dp2[i - 1] + a[i], a[i]);
    }
    int s2 = 1e9;
    int total = 0;
    int pf2 = 0;
    for(int i = 1; i <= n; i++) {
        total += a[i];
        if(dp2[i] < s2) {
            s2 = dp2[i];
            pf2 = i;
        }
    }
    int s4 = s2;
    int ps2 = 0;
    for(int i = pf2; i >= 1; i--) {
        s4 -= a[i];
        if(s4 == 0) {
            ps2 = i;
            break;
        }
    }
    if(s1 > total - s2) {
        cout << s1 << ' ' << ps1 << ' ' << pf1 - ps1 + 1; 
    } else {
        if(s1 < total - s2) {
            cout << total - s2 << ' ' << (pf2 + 1) % n << ' ' << n - (pf2 - ps2 + 1);
        } else {
            if(ps1 <= (pf2 + 1) % n) {
                cout << s1 << ' ' << ps1 << ' ' << pf1 - ps1 + 1; 
            } else {
                cout << total - s2 << (pf2 + 1) % n << ' ' << n - (pf2 - ps2 + 1);
            }
        }
    }
    //cout << max(s1, total - s2) << ' ' << 1 << ' ' << 1;
}