Cod sursa(job #26126)

Utilizator sima_cotizoSima Cotizo sima_cotizo Data 5 martie 2007 11:21:00
Problema Buline Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <stdio.h>
#define FIN "buline.in"
#define FOUT "buline.out"
#define MAX 200001
#define inf 0x3f3f3f

long A[MAX], S[MAX], T[MAX][2];
long N;
long Max = -inf, PM=inf, LM = inf;

int main() {
	long i, x, st = 1, fi=1;

	freopen(FIN, "r", stdin);
	scanf("%ld", &N);
	long Sum = 0;
	S[0] = 0; T[0][0] = -inf;
	for (i=1; i<=N; ++i) {
		scanf("%ld %ld", A+i, &x);
		if ( x==0 ) 
			A[i] *= -1;
		S[i] = S[i-1] + A[i];

		if ( T[i-1][0] < S[i] ) {
			T[i][0] = S[i];
			T[i][1] = i;
		}
		else {
			T[i][0] = T[i-1][0];
			T[i][1] = T[i-1][1];
		}

		if  ( Sum + A[i] > A[i] )   {
			Sum += A[i], fi = i;
		} 
		else {
			Sum = A[i]; fi = i; st = i;
		}
		if ( Max < Sum )
			Max = Sum, PM = inf, LM = inf;
		if ( Max == Sum ) {
			if ( PM > st ) 
				PM=st;
			if ( PM==st &&  LM > fi-st+1 ) 
				LM = fi-st+1;
		}
	}
	fclose(stdin);

	for (i=2; i<=N; ++i) {
		if ( Max < S[N] - S[i-1] + T[i-1][0] ) 
			Max = S[N] - S[i-1] + T[i-1][0], PM = inf, LM = inf;
		if ( Max == S[N] - S[i-1] + T[i-1][0] ) {
			if ( PM > i ) 
				PM = i;
			if ( PM==i && LM > T[i][1] + N-i+1) 
				LM = T[i][1] + N-i+1;
		}
	}

	freopen(FOUT, "w", stdout);
	printf("%ld %ld %ld\n", Max, PM, LM);
	fclose(stdout);
	return 0;
}