Cod sursa(job #26095)

Utilizator gcosminGheorghe Cosmin gcosmin Data 5 martie 2007 10:23:24
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
#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;
}