Cod sursa(job #41407)

Utilizator ProstuStefan-Alexandru Filip Prostu Data 28 martie 2007 11:35:27
Problema Buline Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.87 kb
#include <cstdio>

const int NMAX = 1 << 18;
const int INF = 0x3f3f3f3f;

int N, S, mn, st, l, g, p;
int A[NMAX];

void read() {
	FILE *fin = fopen("buline.in", "rt");
	int i, t;

	fscanf(fin, " %d", &N);

	g = -INF;

	for (i = 0; i < N; ++i) {
		fscanf(fin, " %d %d", A + i, &t);

		if (t == 0) A[i] = -A[i];

		if (A[i] > g)
			g = A[i], p = i;

		S += A[i];
	}

	fclose(fin);
}

void maxim_seq() {
	int i, s, cs;

	mn = st = l = 0;

	for (cs = -1, s = i = 0; i < N; ++i) {
		s += A[i];

//		printf("%d\n", s);

		if (s < mn || (s == mn && st == cs + 1))
			mn = s, st = cs + 1, l = i - cs;

		if (s > 0) s = 0, cs = i;
	}
}

void write() {
	FILE *fout = fopen("buline.out", "wt");

	if (S - mn > 0)
		fprintf(fout, "%d %d %d\n", S - mn, (st + l) % N + 1, N - l);
	else
		fprintf(fout, "%d %d 1\n", g, p + 1);

	fclose(fout);
}

int main() {

	read();

	maxim_seq();

	write();

	return 0;
}