Cod sursa(job #25835)

Utilizator tudalexTudorica Constantin Alexandru tudalex Data 4 martie 2007 15:05:49
Problema Buline Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.1 kb
#include <stdio.h>
int v[200001],
    s[2][200001],
    e[2][200001];
int i,a,b,n;
void solve()
{
	int sum_m,sum_c,p_i,in,sf,i,x,y,q,part,poz=0,max;
	sum_m=v[1];
	sum_c=sum_m;
	p_i=1;
	in=1;
	sf=1;
	for (i=2;i<=n;++i)
	{
		if (sum_c<0) 
		{
			sum_c=v[i];
			p_i=i;
		} else sum_c+=v[i];
		if (sum_c>sum_m)
		{
			sum_m=sum_c;
			in=p_i;
			sf=i;
		}
	}
	max=0;
	part=0;
	poz=0;
	for (i=1;i<=n;++i) 
	{
		part+=v[i];
		if (max<part) 
		{
			max=part;
			poz=i;
		}
		s[0][i]=max;
		e[0][i]=poz;
		
	}
	max=0;
	part=0;
	poz=0;
	for (i=n;i>0;--i) 
	{
		part+=v[i];
		if (max<part)
		{
			max=part;
			poz=i;
		}
		s[1][i]=max;
		e[1][i]=poz;
	}
	//q=-1;
	for (i=1;i<=n-1;++i) 
	if (sum_m<s[0][i]+s[1][i+1])
	{ 
		sum_m=s[0][i]+s[1][i+1]; 
		in=e[1][i]; 
		sf=e[0][i];
	}
	/*else if (sum_m==(s[0][i]+s[1][i+1]))
	{*/
		
	if (in>sf) printf("%d %d %d\n",sum_m,in,n-in+1+sf); else printf("%d %d %d\n",sum_m,in,sf-in+1);
}
		
int main()
{
	freopen("buline.in","r",stdin);
	freopen("buline.out","w",stdout);
	scanf("%d",&n);
	for (i=1;i<=n;++i)
	{
		scanf("%d %d",&a,&b);
		if (b>0) v[i]=a; else v[i]=-1*a;
	}
	solve();
	return 0;
}