Pagini recente » Cod sursa (job #621956) | Cod sursa (job #1096001) | Cod sursa (job #2766349) | Cod sursa (job #1323921) | Cod sursa (job #714109)
Cod sursa(job #714109)
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
using namespace std;
#define maxN 400010
#define inf (1 << 30)
int A[maxN], sum[maxN];
int D[maxN];
int main()
{
freopen ("buline.in", "r", stdin);
freopen ("buline.out", "w", stdout);
int N;
scanf ("%d", &N);
int st = 1, dr = 0;
for (int i = 1; i <= N; ++ i)
{
int code;
scanf ("%d %d", &A[i], &code);
if (! code) A[i] = - A[i];
sum[i] = sum[i - 1] + A[i];
if (st <= dr && i - D[st] >= N) ++ st;
while (st <= dr && sum[D[dr]] >= sum[i]) -- dr;
D[++ dr] = i;
}
int ans = - inf, start = 0, fin = 0;
for (int i = N + 1; i <= 2 * N; ++ i)
{
A[i] = A[i - N];
sum[i] = sum[i - 1] + A[i];
if (st <= dr && i - D[st] >= N) ++ st;
while (st <= dr && sum[D[dr]] >= sum[i]) -- dr;
D[++ dr] = i;
if (ans < sum[i] - sum[D[st]])
{
ans = sum[i] - sum[D[st]];
start = D[st] + 1;
fin = i;
}
}
printf ("%d %d %d", ans, start, fin - start + 1);
return 0;
}