Pagini recente » Cod sursa (job #2918820) | Cod sursa (job #1360818) | Cod sursa (job #1357745) | Cod sursa (job #1343925) | Cod sursa (job #2923949)
#include <bits/stdc++.h>
using ll = long long;
const int MAX_N = 200000;
int a[2 * MAX_N + 1];
ll sp[2 * MAX_N + 1];
std::deque<int> dq;
void update(ll &sum, int &pos, int &len, int sum_, int pos_, int len_) {
if (sum < sum_) {
sum = sum_;
pos = pos_;
len = len_;
} else if (sum == sum_ && pos_ < pos) {
pos = pos_;
len = len_;
} else if (sum == sum_ && pos_ == pos && len_ < len) {
len = len_;
}
}
void insert(int i) {
while (!dq.empty() && sp[i] < sp[dq.back()]) {
dq.pop_back();
}
dq.push_back(i);
}
int main() {
std::ifstream fin("buline.in");
std::ofstream fout("buline.out");
int n;
fin >> n;
for (int i = 1; i <= n; i++) {
int t;
fin >> a[i] >> t;
if (t == 0) {
a[i] *= -1;
}
}
for (int i = n + 1; i <= 2 * n; i++) {
a[i] = a[i - n];
}
for (int i = 1; i <= 2 * n; i++) {
sp[i] = sp[i - 1] + a[i];
}
ll sum = 0;
int pos = (1 << 30), len = (1 << 30);
dq.push_back(0);
for (int i = 1; i <= n; i++) {
update(sum, pos, len, sp[i] - sp[dq.front()], dq.front() + 1, i - dq.front());
insert(i);
}
for (int i = n + 1; i <= 2 * n; i++) {
if (dq.front() == i - n - 1) {
dq.pop_front();
}
update(sum, pos, len, sp[i] - sp[dq.front()], dq.front() + 1, i - dq.front());
insert(i);
}
fout << sum << " " << pos << " " << len;
return 0;
}