Cod sursa(job #238622)

Utilizator antoanelaAntoanela Siminiuc antoanela Data 2 ianuarie 2009 19:39:15
Problema Buline Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.9 kb
#include <stdio.h>

#define lm 200010

long v[lm],p[lm],a[lm],n,i,max,x,poz,l,y;

int main()
{   freopen("buline.in","r",stdin);
	freopen("buline.out","w",stdout);
	scanf("%ld",&n);
	for (i=1; i<=n; i++)
	{   scanf("%ld %ld",&x,&y);
		if (y==0) v[i]=-x; else v[i]=x;
	}
	x=0;
	max=-(1<<30 -1)*2;
	for (i=1; i<=n; i++)
	{	if (x+v[i]>v[i])
	    {   x+=v[i];
 		    p[i]=p[i-1];
        } else
		{   x=v[i];
		    p[i]=i;
        }
		if (x>max)
		{   max=x;
			poz=p[i];
			l=i-p[i]+1;
		}
	}
	a[n+1]=-((1<<30)-1)*2;
	for (i=n; i>1; i--)
		if (a[i+1]+v[i]>v[i]) a[i]=a[i+1]+v[i]; else a[i]=v[i];
	for (i=n; i>1; i--)
		if (a[i]<a[i+1])
		{   a[i]=a[i+1];
		    p[i]=p[i+1];
        } else p[i]=i;
	x=a[2];
	a[1]=a[2];
	for (i=1; i<n; i++)
	{	x+=v[i];
		x-=a[i]-a[i+1];
		if (x>max)
		{   max=x;
			poz=p[i+1];
			l=i+n-p[i+1]+1;
		}
	}
	printf("%ld %ld %ld",max,poz,l);
}