Cod sursa(job #526375)

Utilizator matei_cChristescu Matei matei_c Data 28 ianuarie 2011 10:33:19
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.44 kb
#include<stdio.h> //p=??? l=???
int modul(int x)
{
	if(x<0)
		return -x;
	return x;
}

int n,S,Smax,l,p,Lmin=10000000,Pmin=10000000,nr,ok,end;
int sume[400002],t[400002],x[400002],v[400002];
int main()
{
	int i;
	freopen("buline.in","r",stdin);
	freopen("buline.out","w",stdout);
	scanf("%d",&n);
	for(i=1;i<=n;i++)
	{
		scanf("%d%d",&nr,&ok);
		if(ok==0)
			v[i]=-nr;
		if(ok==1)
			v[i]=nr;
	}	
	for(i=1;i<=n-1;i++)
		v[n+i]=v[i];
	sume[1]=v[1];
	for(i=2;i<=2*n-1;i++)
		sume[i]=sume[i-1]+v[i];
	//////////////////////////////////////////////////////////
	Smax=-2000000000;
	int first = 1, last = 1;	
	x[1]=sume[1];
	t[1] = 1;
	for(i=2;i<=2*n-1 ;i++)
	{
		while(sume[i] > x[last] && last >= first)
			last--;
		x[ ++last ] = sume[ i ];
		t[ last ] = i;
		if( t[ first ] + n <= i ) first++;
		if(i < n) continue;
		S= x[first]-sume[ i - n ];
		end=t[first];
		p=i-n+1;
		l=modul(end-p)+1;
		if(S>Smax && i >= n)
		{	
			Smax=S;
			Lmin=l;
			Pmin=p;
		}	
		if(S==Smax && i>=n)
		{
			if(p<Pmin)
				Pmin=p;
			else
				if(l<Lmin)
					Lmin=l;
		}	
	}
	////////////////////////////////////
	for(i=2*n;last>=first;i++)
	{
		if( t[ first ] + n <= i ) first++;
		if(first > last) break;
		S= x[first]-sume[ i - n ];
		end=t[first];
		p=i-n+1;
		l=modul(end-p)+1;
		if(S>Smax && i >= n)
		{	
			Smax=S;
			Lmin=l;
			Pmin=p;
		}	
		if(S==Smax && i>=n)
		{
			if(p<Pmin)
				Pmin=p;
			else
				if(l<Lmin)
					Lmin=l;
		}	
	}
	printf("%d %d %d\n",Smax,Pmin,Lmin);
	return 0;
}