Cod sursa(job #673813)

Utilizator ciuscatalincius catalin ciuscatalin Data 4 februarie 2012 22:04:07
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.14 kb
# include <fstream>
using namespace std;
ifstream f ("buline.in");
ofstream g ("buline.out");
int a[200005],best[200005],l[200005],l2[200005],s1[200005],s2[200005];
int lg,maxim,p,n,i,x,s,max2,poz;
int main ()
{
	f>>n;
	for (i=1;i<=n;i++)
	{
		f>>a[i];
		f>>x;
		if(x==0)
		a[i]=-a[i];
	}
	best[1]=a[1];
	l[1]=1;
	for(i=2;i<=n;i++)
		if(best[i-1]+a[i]>a[i])
		{
			best[i]=best[i-1]+a[i];
			l[i]=l[i-1]+1;
		}
		else
		{
			best[i]=a[i];
			l[i]=1;
		}
		maxim=-2000000000;
		for(i=1;i<=n;i++)
			if(best[i]>maxim)
			{
				maxim=best[i];
				p=i-l[i]+1;
				lg=l[i];
			}
			s=0;
			max2=-2000000000;
			for(i=1;i<=n;i++)
			{
				s+=a[i];
				if (max2<s)
				{
					max2=s;
					l[i]=i;
				}
				else
				l[i]=l[i-1];
				s1[i]=max2;
			}
			s=0;
			max2=-2000000000;
			for(i=n;i>=1;i--)
			{
				s+=a[i];
				if (max2<s)
				{
					max2=s;
					l2[i]=i;
				}
				else
					l2[i]=l2[i+1];
				s2[i]=max2;
			}
			for (i=2;i<=n;i++)
				if (s2[i]+s1[i-1]>maxim)
				{
					maxim=s2[i]+s1[i-1];
					p=l2[i];
					lg=(n-l2[i]+1)+l[i-1];
				}

		g<<maxim<<" "<<p<<" "<<lg;
		return 0;
}