Pagini recente » Cod sursa (job #367442) | Cod sursa (job #548794) | Cod sursa (job #2963282) | Cod sursa (job #2311072) | Cod sursa (job #26095)
Cod sursa(job #26095)
#include <stdio.h>
#define NMAX 400010
#define INF 2000000000
int N;
int a[NMAX];
int deck[NMAX];
inline int MAX(int a, int b) { return (a > b) ? a : b; }
int main()
{
int i, p, q, smn, beg = 0, end = 0;
freopen("buline.in", "r", stdin);
freopen("buline.out", "w", stdout);
scanf("%d", &N);
for (i = 1; i <= N; i++) {
scanf("%d %d", &a[i], &smn);
if (!smn) a[i] *= -1;
}
for (i = N + 1; i <= 2 * N; i++) a[i] = a[i - N];
p = q = 0;
deck[0] = 0;
int max = -INF;
for (i = 1; i <= 2 * N; i++) {
a[i] += a[i-1];
while (p <= q && deck[p] < i - N) p++;
if (p <= q) {
if (a[i] - a[deck[p]] > max) {
max = a[i] - a[deck[p]];
beg = deck[p]+1;
end = i;
}
} else {
if (a[i] - a[i-1] > max) {
max = a[i] - a[i-1];
beg = i;
end = i;
}
}
while (p <= q && a[deck[q]] > a[i]) q--;
deck[++q] = i;
}
printf("%d %d %d\n", max, beg, end - beg + 1);
fclose(stdin);
fclose(stdout);
return 0;
}