Pagini recente » Cod sursa (job #886523) | Cod sursa (job #1850790) | Cod sursa (job #592560) | tema | Cod sursa (job #2462883)
#include <iostream>
#include <cctype>
#include <cstdio>
#include <map>
#include <queue>
using namespace std;
const int SIZE = 1 << 17;
int pointer = SIZE;
char buffer[SIZE];
char Advance() {
if (pointer == SIZE) {
fread(buffer, 1, SIZE, stdin);
pointer = 0;
}
return buffer[pointer++];
}
int Read() {
int answer = 0;
char ch = Advance();
while (!isdigit(ch))
ch = Advance();
while (isdigit(ch)) {
answer = answer * 10 + ch - '0';
ch = Advance();
}
return answer;
}
typedef long long ll;
const int N = 200000 + 7;
int n;
ll sum[2 * N];
priority_queue <pair <ll, int>> pq;
map <pair <ll, int>, bool> del;
int main() {
freopen ("buline.in", "r", stdin);
freopen ("buline.out", "w", stdout);
n = Read();
for (int i = 1; i <= n; i++) {
int x = Read(), y = Read();
if (y == 0) {
sum[i] = -x;
} else {
sum[i] = +x;
}
sum[i + n] = sum[i];
}
for (int i = 1; i <= 2 * n; i++) {
sum[i] += sum[i - 1];
}
for (int i = 0; i < n; i++) {
pq.push({sum[i], -i});
}
ll best = -(1LL << 60);
int start, len;
for (int i = 1; i <= n; i++) {
pq.push({sum[i + n - 1], -(i + n - 1)});
while (del[pq.top()]) {
pq.pop();
}
pair <ll, int> it = pq.top();
ll cur = it.first - sum[i - 1];
if (cur > best) {
best = cur;
start = i;
len = -it.second - i + 1;
}
del[ {sum[i - 1], -(i - 1)}] = 1;
}
cout << best << ' ' << start << ' ' << len << '\n';
return 0;
}