Cod sursa(job #26640)

Utilizator MariusMarius Stroe Marius Data 5 martie 2007 20:00:51
Problema Buline Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.74 kb
#include <cstdio>
using namespace std;

const char iname[] = "buline.in";
const char oname[] = "buline.out";

#define MAX_N 400005

int A[MAX_N];

int main(void) {
	freopen(iname, "r", stdin);
	int n;
	int i;
	int res, start, length;
	int min, sum, p;
	int color;
	for (scanf("%d", & n), i = 1; i <= n; ++ i) {
		scanf("%d %d", A + i, & color);
		if (color == 0)
			A[i] = - A[i];
		A[i + n] = A[i];
	}
    res = A[0], start = 0, length = 1;
	min = sum = 0, p = 0;
	for (i = 1; i < n << 1; ++ i) {
		sum = sum + A[i];
		if (res < sum - min)
			res = sum - min, start = p, length = i - p;
		if (min > sum)
			min = sum, p = i;
	}
	freopen(oname, "w", stdout);
	printf("%d %d %d\n", res, start + 1, length);
	return 0;
}