Pagini recente » Cod sursa (job #155927) | Cod sursa (job #1559695) | Cod sursa (job #1605738) | Cod sursa (job #2058605) | Cod sursa (job #1532408)
#include <cstdio>
#include <deque>
#include <algorithm>
using namespace std;
int v[400010];
deque <int> dq;
int main ()
{
freopen ("buline.in", "r", stdin);
freopen ("buline.out", "w", stdout);
int n;
scanf ("%d", &n);
for (int i = 1;; ++i)
{
int x, y;
scanf ("%d %d", &x, &y);
y = !y ? -1 : 1;
y *= x;
v[i] = v[i - 1] + y;
v[i + n] = y;
if (i == n) break;
while (!dq.empty () && v[i] >= v[dq.back ()])
dq.pop_back ();
dq.push_back (i);
}
for (int i = n + 1; i < 2 * n; ++i)
v[i] += v[i - 1];
int ma = -100000, poz, len;
for (int i = n; i < 2 * n; ++i)
{
if (!dq.empty () && dq.front () <= i - n) dq.pop_front ();
while (!dq.empty () && v[i] >= v[dq.back ()])
dq.pop_back ();
dq.push_back (i);
if (v[dq.front ()] - v[i - n] > ma) ma = v[dq.front ()] - v[i - n], poz = i - n + 1, len = dq.front () - (i - n);
}
printf ("%d ", ma);
printf ("%d ", poz);
printf ("%d\n", len);
return 0;
}