Pagini recente » Cod sursa (job #910387) | Cod sursa (job #700804) | Cod sursa (job #2607728) | Cod sursa (job #2422522) | Cod sursa (job #714119)
Cod sursa(job #714119)
#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];
while (st <= dr && sum[D[dr]] >= sum[i]) -- dr;
D[++ dr] = i;
}
int ans = - inf, start = 0, leng = 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;
leng = i - start + 1;
}
else if (ans == sum[i] - sum[D[st]] && leng > i - (D[st] + 1) + 1)
{
start = D[st] + 1;
leng = i - start + 1;
}
}
printf ("%d %d %d", ans, start, leng);
return 0;
}