Pagini recente » Cod sursa (job #1965143) | Cod sursa (job #916581) | Cod sursa (job #886381) | Cod sursa (job #2763063) | Cod sursa (job #3161586)
#include <iostream>
#include <fstream>
#include <climits>
#include <deque>
#define ll long long
using namespace std;
ifstream fin("buline.in");
ofstream fout("buline.out");
const ll NMAX = 2e5 + 5;
ll s[2 * NMAX], n, res = INT_MIN, start, lun;
deque<pair<ll, ll> > dq;
int main() {
fin >> n;
for (ll i = 1; i <= n; i++) {
bool alb;
ll x;
fin >> x >> alb;
if (!alb)
x = -x;
s[i] = s[i - 1] + x;
s[i + n] = x;
ll smin = (!dq.empty() ? dq.front().first : s[1]);
ll ind = (!dq.empty() ? dq.front().second : 1);
if (s[i] - smin > res || (s[i] - smin == res && i - ind < lun)) {
res = s[i] - smin;
start = ind + 1;
lun = i - ind;
}
while (!dq.empty() && s[i] < dq.back().first) {
dq.pop_back();
}
dq.push_back(make_pair(s[i], i));
}
for (ll i = n + 1; i <= 2 * n; i++) {
s[i] += s[i - 1];
while (!dq.empty() && dq.front().second < i - n) {
dq.pop_front();
}
ll smin = (!dq.empty() ? dq.front().first : s[1]);
ll ind = (!dq.empty() ? dq.front().second : 1);
if (s[i] - smin > res || (s[i] - smin == res && i < start) || (s[i] - smin == res && i - ind < lun)) {
res = s[i] - smin;
start = ind + 1;
lun = i - ind;
}
while (!dq.empty() && s[i] < dq.back().first) {
dq.pop_back();
}
dq.push_back(make_pair(s[i], i));
}
if (start > n)
start -= n;
fout << res << ' ' << start << ' ' << lun;
return 0;
}