Cod sursa(job #26757)

Utilizator MariusMarius Stroe Marius Data 5 martie 2007 21:01:33
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.97 kb
#include <cstdio>
using namespace std;

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

#define MAX_N 200005

int A[MAX_N], S[MAX_N], T[MAX_N], P[MAX_N];

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