Cod sursa(job #127829)

Utilizator za_wolfpalianos cristian za_wolf Data 25 ianuarie 2008 01:23:47
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.4 kb
#include<stdio.h>
#define NMAX 500001
long y[NMAX],z[NMAX],x[NMAX],a,b,i,k,l,p,poz,max,m,s,lung,n;
long maxim(long a,long b)
{
	if (a>b) return a;
	return b;
}

int main()
{
	freopen("buline.in","r",stdin);
	freopen("buline.out","w",stdout);
	scanf("%ld",&n);
	for (i=1;i<=n;i++)
	{
		scanf("%ld%ld",&a,&b);
		if (b==0) x[i]=0-a;
		else
			x[i]=a;
		x[n+i]=x[i];
	}
/*	s=x[1];
	l=1;
	p=1;
	max=s;
	lung=l;
	poz=p;
	m=n+n;
	for (i=1;i<=m;i++)
	if (l<=n)
	{
		if (s+x[i]<0)
		{
			if (s>max)
			{
				max=s;
				poz=p;
				lung=l;
			}
			s=x[i];
			l=1;
			p=i;
		} else
		{
			if (s>max)
			{
				max=s;
				poz=p;
				lung=l;
			}
			s+=x[i];
			l++;
		}
	}
 /*	else
	{
		p=p+1;
		l=0;
		s=0;
	}
 */
	s=x[1];
	p=1;
	l=1;
	max=s;
	for (i=2;i<=n;i++)
	{
		if (s+x[i]<0)
		{
			if (s>max)
			{
				max=s;
				poz=p;
				lung=l+1;
			}
			p=i+1;
			l=0;
			s=0;
		} else
		{
			if (s>max)
			{
				max=s;
				poz=p;
				lung=l;
			}
				s+=x[i];

				l++;
		}

	}
	for (i=1;i<=n;i++)
		y[i]=y[i-1]+x[i];
	z[1]=y[1];
	for (i=2;i<=n;i++)
		z[i]=maxim(z[i-1],y[i]);
	for (i=2;i<=n;i++)
	{
		s=z[i-1]+y[n]-y[i-1];
		if (s>max)
		{
			max=s;
			poz=i;
			lung=-1000;
		}
	}

	if (lung==-1000)
	{
		s=0;
		for (i=poz;s!=max;i++)
		s+=x[i];
		i--;
		lung=i-poz+1;
	}
	printf("%ld %ld %ld\n",max,poz,lung);



	return 0;
}