Cod sursa(job #25824)

Utilizator slayer4uVictor Popescu slayer4u Data 4 martie 2007 15:01:28
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.05 kb
#include<stdio.h>
long n,sum,lg1[200001],ind2[200001],x[200001],max1[200002],max2[200002],i,a,b,inc,lg,lgmax,incmax,maxon,s1,s2;
int main()
{
	freopen ("buline.in","rt",stdin);
	freopen ("buline.out","wt",stdout);
	
	scanf("%ld",&n);

	for (i=1;i<=n;i++)
	{
		scanf("%ld %ld",&a,&b);
		x[i]=b==0?-a:a;
	}

	sum=0;
	inc=1;
	for (i=1;i<=n;i++)
	{
		
		sum+=x[i];
		lg++;
		if (sum>maxon)
		{
			maxon=sum;
			incmax=inc;
			lgmax=lg;
		}
		if (sum<0)
		{
			sum=0;
			inc=i+1;
			lg=0;

		}
	}

	for (i=1;i<=n;i++)
	{
		s1+=x[i];
		if (s1>max1[i-1])
		{
			max1[i]=s1;
			lg1[i]=i;
		}
		else
		{
			max1[i]=max1[i-1];
			lg1[i]=lg1[i-1];
		}
	}

	for (i=n;i>=1;i--)
	{
		s2+=x[i];
		if (s2>max2[i+1])
		{
			max2[i]=s2;
			ind2[i]=i;
		}
		else
		{
			max2[i]=max2[i+1];
			ind2[i]=ind2[i+1];
		}
	}

	for (i=1;i<=n;i++)
		if (max1[i]+max2[i+1]>maxon)
		{
			maxon=max1[i]+max2[i+1];
			incmax=ind2[i+1];
			lgmax=lg1[i]+n-ind2[i+1]+1;
		}

	printf("%ld %ld %ld\n",maxon,incmax,lgmax);
	return 0;
}