Pagini recente » Cod sursa (job #3361587) | Cod sursa (job #3362080) | Cod sursa (job #3362069) | Cod sursa (job #3362083) | Cod sursa (job #3361287)
#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);
}