Cod sursa(job #3361287)

Utilizator adimiclaus15Miclaus Adrian Stefan adimiclaus15 Data 22 iulie 2026 20:20:04
Problema Buline Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.1 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;
    for(int i = 1; i <= n; i++) {
        if(dp1[i] > s1) {
            s1 = dp1[i];
        }
    }
    //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;
    for(int i = 1; i <= n; i++) {
        total += a[i];
        if(dp2[i] < s2) {
            s2 = dp2[i];
        }
    }
    cout << max(s1, total - s2);
}