Cod sursa(job #25027)

Utilizator Adriana_SAdriana Sperlea Adriana_S Data 4 martie 2007 09:56:05
Problema Buline Scor 20
Compilator cpp Status done
Runda preONI 2007, Runda 3, Clasa a 9-a si gimnaziu Marime 0.86 kb
#include <stdio.h>

const int N_MAX = 400010;

int v[N_MAX];

int main()
{
	freopen("buline.in", "r", stdin);
	freopen("buline.out", "w", stdout);

	int N, k, i;

	scanf("%d\n", &N);
	for (i = 1; i <= N; i ++) {
		scanf("%d %d\n", &v[i], &k);
		if (k == 0) {
			v[i] *= (-1);
		}
	}

	for (i = 1; i <= N; i ++) {
		v[N + i] = v[i];
	}
	N *= 2;

	int MAX = v[1], sc = v[1];
	int ic = 1, sf = 1, pc = 1;

	for (i = 2; i <= N; i ++) {
		if (sc > 0) {
			sc += v[i];
		} else {
			sc = v[i];
			pc = i;
		}

		if (i - pc + 1 > N / 2) {
			sc = v[i];
			pc = i;
		}

		if (MAX < sc) {
			MAX = sc;
			ic = pc;
			sf = i;
		} else {
			if (MAX == sc) {
				if (pc < ic) {
					ic = pc;
					sf = i;
				} else {
					if (pc == ic && i < sf) {
						sf = i;
					}
				}
			}
		}
	}

	int L = sf - ic + 1;
	if (ic > N) {
		ic -= N;
	}
	printf("%d %d %d\n", MAX, ic, L);
	
	return 0;
}