Cod sursa(job #41529)

Utilizator ProstuStefan-Alexandru Filip Prostu Data 28 martie 2007 12:37:22
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.11 kb
#include <cstdio>

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

int N;
long long S[NMAX], Q[NMAX], mx;
int poz[NMAX];
int str, l;

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;
	}

	for (i = 1; i <= N; ++i)
		S[N + i] = S[N] + S[i];

	fclose(fin);
}

void insert(long long Q[], int &st, int &dr, long long v, int p) {
	while (st <= dr && poz[st] + N <= p) ++st;
	while (st <= dr && Q[dr] > v) --dr;

	++dr;
	Q[dr] = v; poz[dr] = p;
}

void solve() {
	int i, st, dr;

	st = 0; dr = -1;
	for (i = 0; i < N; ++i)
		insert(Q, st, dr, S[i], i);

	mx = - ((long long)INF * INF);
	for (i = N; i <= (N << 1); ++i) {
//		printf("%lld %d\n", Q[st], poz[st]);
		if (mx < S[i] - Q[st])
			mx = S[i] - Q[st],
			str = poz[st] + 1,
			l = i - poz[st];
		insert(Q, st, dr, S[i], i);
	}
}

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

	fprintf(fout, "%lld %d %d\n", mx, str > N ? str - N : str, l);

	fclose(fout);
}

int main() {

	read();

	solve();

	write();

	return 0;
}