Cod sursa(job #26579)

Utilizator surcauvsurcau vasile surcauv Data 5 martie 2007 18:57:53
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.69 kb
# include <stdio.h>

# define  _fin  "buline.in"
# define  _fout "buline.out"

# define  maxn  400002


int a[maxn], n, smax, p, l;


int main()
{
	freopen(_fin, "r", stdin);
	freopen(_fout,"w", stdout);
	
	int i, pz=1, saux=0, x, s=0, t;
	
	for (scanf("%d", &n), i=1; i<=n; i++)
	{
		scanf("%d%d", a+i, &x), a[i] *= (2*x-1);
		s += a[i];
		
		if ( saux+a[i] >= a[i] ) saux += a[i];
		else saux = a[i], pz=i;
		
		if ( saux>smax ) smax=saux, p=pz, l=i-pz+1;
	}
	
	for (saux=0, t=-10001, i=1; i<=n; i++)
	{
		saux+=a[i];
		if ( saux>t ) t=saux, pz=n+i;
		
		if ( s-saux+t > smax ) smax=s-saux+t, p=i+1, l=pz-i;
	}
	
	printf("%d %d %d\n", smax, p, l);
	
	return 0;
}