Cod sursa(job #644892)

Utilizator ProcopliucProcopliuc Adrian Procopliuc Data 7 decembrie 2011 19:28:43
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.15 kb
# include <fstream>
using namespace std;
ifstream f ("buline.in");
ofstream g ("buline.out");
int a[200005],best[200005],l[200005],lg,maxim,p,n,i,x,s,max2,poz,l2[200005],s1[200005],s2[200005];
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;
}