Pagini recente » Cod sursa (job #36015) | Cod sursa (job #2417140) | Cod sursa (job #1074482) | Cod sursa (job #1463986) | Cod sursa (job #2121430)
#include <fstream>
#define limit 200005
using namespace std;
ifstream f("buline.in");
ofstream g("buline.out");
int n, x, sum, mx, mx2, index, length, v[limit], best[limit], lg[limit], S1[limit], lg2[limit], S2[limit];
int main()
{
f >> n;
for (int i = 1; i <= n; i++) {
f >> v[i] >> x;
if (!x) v[i] *= -1;
}
best[1] = v[1];
lg[1] = 1;
for (int i = 2; i <= n; i++)
if (best[i - 1] + v[i] > v[i]) {
best[i] = best[i - 1] + v[i];
lg[i] = lg[i - 1] + 1;
}
else {
best[i] = v[i];
lg[i] = 1;
}
mx = -2000000000;
for (int i = 1; i <= n; i++)
if (best[i] > mx) {
mx = best[i];
index = i - lg[i] + 1;
length = lg[i];
}
mx2 = -2000000000;
for (int i = 1; i <= n; i++) {
sum += v[i];
if (mx2 < sum) {
mx2 = sum;
lg[i] = i;
}
else lg[i] = lg[i - 1];
S1[i] = mx2;
}
sum = 0, mx2 = -2000000000;
for (int i = n; i >= 1; i--) {
sum += v[i];
if (mx2 < sum) {
mx2 = sum;
lg2[i] = i;
}
else lg2[i] = lg2[i + 1];
S2[i] = mx2;
}
for (int i = 2; i <= n; i++)
if (S2[i] + S1[i - 1] > mx) {
mx = S2[i] + S1[i - 1];
index = lg2[i];
length = (n - lg2[i] + 1) + lg[i - 1];
}
g << mx << ' ' << index << ' ' << length;
f.close();
g.close();
return 0;
}