Pagini recente » Cod sursa (job #2874092) | Cod sursa (job #240231) | Cod sursa (job #263088) | Cod sursa (job #1794193) | Cod sursa (job #3244578)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("buline.in");
ofstream fout("buline.out");
using ll = long long;
int n;
vector<int> v(200001);
vector<bool> hasBeenStart(200001);
struct a {
ll value;
int index;
int length;
} curr, ans, ans2;
int main() {
fin >> n;
for (int i = 1; i <= n; i++) {
short type;
fin >> v[i] >> type;
if (!type) {
v[i] *= -1;
}
}
curr = ans = {v[1],1,1};
hasBeenStart[1] = true;
for (int i = 2; curr.length < n; i++, i = i > n ? 1 : i) {
if (curr.value + v[i] >= v[i]) {
curr.length++;
curr.value += v[i];
if (ans.value < curr.value) {
ans = curr;
} else if (ans.value == curr.value and (ans.length < curr.length or ans.index < curr.index)) {
ans = curr;
}
} else {
curr.value = v[i];
curr.length = 1;
curr.index = i;
if (hasBeenStart[i] == true) {
break;
}
hasBeenStart[i] = true;
if (ans.value < curr.value) {
ans = curr;
} else if (ans.value == curr.value and (ans.length < curr.length or ans.index < curr.index)) {
ans = curr;
}
}
}
curr = ans2 = {v[1],1,1};
hasBeenStart = vector<bool>(200001, false);
hasBeenStart[1] = true;
for (int i = 2; curr.length < n; i++, i = i > n ? 1 : i) {
if (curr.value + v[i] <= v[i]) {
curr.length++;
curr.value += v[i];
if (ans2.value > curr.value) {
ans2 = curr;
} else if (ans2.value == curr.value and (ans2.length > curr.length or ans2.index > curr.index)) {
ans2 = curr;
}
} else {
curr.value = v[i];
curr.length = 1;
curr.index = i;
if (hasBeenStart[i] == true) {
break;
}
hasBeenStart[i] = true;
if (ans2.value > curr.value) {
ans2 = curr;
} else if (ans2.value == curr.value and (ans2.length > curr.length or ans2.index > curr.index)) {
ans2 = curr;
}
}
}
int s = 0;
for (int i = 1; i < ans2.index; i++) {
s += v[i];
}
for (int i = ans2.index + ans2.length; i <= n; i++) {
s += v[i];
}
if (ans.value < s) {
ans.value = s;
ans.index = ans2.index + ans2.length;
ans.length = n - ans2.length;
}
fout << ans.value << ' ' << ans.index << ' ' << ans.length;
return 0;
}