Cod sursa(job #644887)

Utilizator ProcopliucProcopliuc Adrian Procopliuc Data 7 decembrie 2011 18:56:41
Problema Buline Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.84 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;
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];
			}
			max2=-2000000000;
			s=0;
		for (i=1;i<n-l[n]+1;i++)
		{
			s+=a[i];
			if (max2<s)
			{
				max2=s;
				poz=i;
			}
		}
			
		if (best[n]+max2>maxim)
		{
			maxim=best[n]+max2;
			p=n-l[n]+1;
			lg=l[n]+poz;
		}
			
		g<<maxim<<" "<<p<<" "<<lg;
		return 0;
}