Cod sursa(job #26609)

Utilizator love_for_uSpancioc Riana love_for_u Data 5 martie 2007 19:20:13
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.99 kb
//100p

#include <stdio.h>
#define MAX(a, b) ( (a) < (b) ? (b) : (a) )
#define NMAX 400001
#define INF 2000001

long long S[NMAX];
long long St[NMAX];
int Poz[NMAX];
int i, j, N, NN, nr, cul;
int s1, s2;
long long max;
int pmax, lmax;

void add(long long e, int pz)
{
	while (s2 >= s1 && St[s2] > e) s2--;

	s2++;

	St[s2] = e;
	Poz[s2] = pz;

	if (pz - Poz[s1] + 1 > N) s1++;
}

int main()
{
	freopen("buline.in", "r", stdin);
	freopen("buline.out", "w", stdout);
	
	scanf("%d", &N);
	
	for (i = 1; i <= N; i++)
	{
		scanf("%d %d", &nr, &cul); 
	
		if (cul == 0) nr =  -nr; 
		
		S[i] = S[i - 1] + nr;
	}		
	
	NN = N;
	
	for (i = 1; i < N; i++)
		S[++NN] = S[i] + S[N];
	
	s1 = s2 = 0;
	
	max = -INF;
	
	for (i = 1; i < NN; i++)
	{
		if (max < S[i] - St[s1])
		{
			max = (long long)S[i] - St[s1];
			pmax = Poz[s1] + 1;
			lmax = i - pmax + 1;
		}
		
		add(S[i], i);
	}
	
	printf("%lld ", max);
	printf("%d %d\n", pmax, lmax);
	

	return 0;
}