Pagini recente » Cod sursa (job #2929495) | Cod sursa (job #167609) | Cod sursa (job #1386815) | Cod sursa (job #1658312) | Cod sursa (job #2588732)
#include <bits/stdc++.h>
#define PLEC fin.close(); fout.close(); return 0;
using namespace std;
ifstream fin("buline.in");
ofstream fout("buline.out");
const int N(5e5 + 5);
int n, v[N], x, sp[N], curr, res(-1e9), start, lenght;
deque<int> dq;
int main()
{
fin >> n;
for (int i = 1; i <= n; ++i)
{
fin >> v[i] >> x;
if (x == 0)
v[i] = -v[i];
sp[i] = sp[i-1] + v[i];
}
for (int i = n + 1; i <= 2 * n; ++i)
{
v[i] = v[i - n];
sp[i] = sp[i-1] + v[i];
}
dq.emplace_back(0);
for (int i = 1; i <= 2 * n; ++i)
{
while (!dq.empty() && i - dq.front() > n)
dq.pop_front();
while (!dq.empty() && sp[i] <= sp[dq.back()])
dq.pop_back();
if (!dq.empty())
{
curr = sp[i] - sp[dq.front()];
if (res < curr)
res = curr, start = dq.front() + 1, lenght = i - dq.front();
}
dq.emplace_back(i);
}
start %= n;
if (start == 0)
start = n;
fout << res << ' ' << start << ' ' << lenght;
PLEC
}