Cod sursa(job #41451)

Utilizator ProstuStefan-Alexandru Filip Prostu Data 28 martie 2007 11:53:15
Problema Buline Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.73 kb
// Strange problem
#include <cstdio>

const int NMAX = 1 << 18;

int N, S[NMAX], T[NMAX], L[NMAX];

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

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

	for (i = 1; i <= N; ++i) {
		fscanf(fin, " %d %d", &v, &t);
		if (t == 0) v = -v;

		S[i] = S[i - 1] + v;
		if (T[i - 1] >= S[i])
			T[i] = T[i - 1], L[i] = L[i - 1];
		else
			T[i] = S[i], L[i] = i;
	}

	fclose(fin);
}

void write() {
	FILE *fout = fopen("buline.out", "wt");
	int i, mx = 0, st = 0, l = 0, aux;

	for (i = 1; i <= N; ++i) {
		aux = T[i - 1] + (S[N] - S[i - 1]);

		if (mx < aux)
			mx = aux,
			st = i, l = N - i + 1 + L[i];
	}

	fprintf(fout, "%d %d %d\n", mx, st, l);

	fclose(fout);
}

int main() {

	read();

	write();

	return 0;
}