Pagini recente » Borderou de evaluare (job #3113037) | Monitorul de evaluare | Monitorul de evaluare | Monitorul de evaluare | Cod sursa (job #3345623)
#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
*/