Cod sursa(job #238642)

Utilizator antoanelaAntoanela Siminiuc antoanela Data 2 ianuarie 2009 20:55:58
Problema Buline Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include <stdio.h>

#define lm 200010
#define lmx 2000000000

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

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=-lmx;
	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]=-lmx;
	for (i=n; i>1; i--)
	{	b[n]=1;
		if (a[i+1]+v[i]>=v[i])
		{   a[i]=a[i+1]+v[i];
 		    b[i]=b[i+1];
        } 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];
			b[i]=b[i+1];
        } else p[i]=i;
	x=a[2];
	a[1]=a[2];
	b[1]=1;
	for (i=1; i<n; i++)
	{	x+=v[i];
		x-=a[i]-a[i+1];
		if ((x>max)&(b[i]==1))
		{   max=x;
			poz=p[i+1];
			l=i+n-p[i+1]+1;
        }
	}
	printf("%ld %ld %ld",max,poz,l);
}