Cod sursa(job #213859)

Utilizator AndreyPAndrei Poenaru AndreyP Data 11 octombrie 2008 20:57:23
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.15 kb
#include<stdio.h>
int s[200005],smax,pmax,lmax,n,max[200005],aux[200005],v[200005];
inline int maxim(int,int);
void citire()
{
	scanf("%d",&n);
	int x,c;
	aux[0]=1;
	for(int i=1; i<=n; i++)
	{
		scanf("%d%d",&x,&c);
		if(c)
		{
			s[i]=s[i-1]+x;
			v[i]=x;
		}
		else
		{
			s[i]=s[i-1]-x;
			v[i]=-x;
		}
		max[i]=maxim(max[i-1],s[i]);
		if(max[i]==max[i-1])
			aux[i]=aux[i-1];
		else
			aux[i]=i;
	}
}
inline int maxim(int x,int y)
{
	if(x>y)
		return x;
	return y;
}
void rezolva()
{
	int sum,lun;
	int s1=0,p1=1,l1=0;
	for(int i=1; i<=n; i++)
	{
		sum=max[i-1]+s[n]-s[i-1];
		lun=aux[i-1]+n-i+1;
		s1+=v[i];
		l1++;
		if(s1>sum)
		{
			if(s1>smax)
			{
				smax=s1;
				pmax=p1;
				lmax=l1;
			}
		}
		else
		{
			if(sum>smax)
			{
				smax=sum;
				pmax=i;
				lmax=lun;
			}
		}
		if(s1<0)
		{
			s1=0;
			p1=i+1;
			l1=0;
		}
	}
}
int main()
{
	freopen("buline.in","r",stdin);
	freopen("buline.out","w",stdout);
	pmax=1<<30;
	smax=-pmax;
	max[0]=smax;
	citire();
	rezolva();
	//if(lmax==n)
	//	printf("%d 1 %d\n",smax,n);
	//else
	printf("%d %d %d\n",smax,pmax,lmax);
	return 0;
}