Cod sursa(job #25037)

Utilizator MaGdUtZaVasile Maria-Magdalena MaGdUtZa Data 4 martie 2007 09:57:29
Problema Buline Scor 0
Compilator cpp Status done
Runda preONI 2007, Runda 3, Clasa a 9-a si gimnaziu Marime 0.8 kb
#include<stdio.h>

#define dim 200001

long a[dim],n,i,nr,cl,max,sc,ic,pc,sf,lmax,j,lmin,min;

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

	scanf("%ld", &n);

	min=n;lmin=n;

	for(i=1; i<=n; ++i)
	{
		scanf("%ld %ld", &nr, &cl);

		if(cl==0)
		{
			a[i]=-nr;

			a[i+n]=a[i];
		}
		else
		{
			a[i]=nr;

			a[i+n]=a[i];
		}
	}
	a[n+n]=0;

	max=a[1];

	sc=a[1];

	ic=1;sf=1;pc=1;

	for(j=2; j<=n; ++j)
	{
		sc=0;

		for(i=j; i<=j+n; ++i)
		{
			if(sc>0)

				sc+=a[i];

			else
			{
				sc=a[i];

				pc=i;
			}
			if(sc>max)
			{
				ic=pc;

				sf=i;

				max=sc;

			}
		}
		if(ic<min)

			min=ic;

		if(sf-ic+1<lmin)

			lmin=sf-ic+1;

	}
	printf("%ld %ld %ld", max, min, lmin);

	return 0;
}