Cod sursa(job #26541)

Utilizator surcauvsurcau vasile surcauv Data 5 martie 2007 18:25:58
Problema Buline Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.71 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, saux, x;
	
	for (scanf("%d", &n), i=1; i<=n; i++)
		 scanf("%d%d", a+i, &x), a[i] *= (2*x-1), a[n+i] = a[i];
	
	smax=saux=a[1], p=pz=l=1;
	if ( saux < 0 ) pz=2, saux=0;
	
	for (i=2; i<=n<<1; i++)
	{
		saux += a[i];

		if ( i-pz+1 > n )
		{
			saux -= a[pz++];
			while ( a[pz] < 0 && pz <= i ) saux -= a[pz++];
		}

		if ( saux > smax )
			smax = saux, p=pz, l=i-pz+1;

		if ( saux < 0 ) saux = 0, pz=i+1;
	}
	
	printf("%d %d %d\n", smax, p, l);
	
	return 0;
}