Pagini recente » Cod sursa (job #3361591) | Cod sursa (job #3361285) | Cod sursa (job #3362072) | Cod sursa (job #3361763) | Cod sursa (job #3361291)
#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;
}