Cod sursa(job #333115)

Utilizator AndreyPAndrei Poenaru AndreyP Data 21 iulie 2009 15:13:35
Problema Buline Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 kb
#include<stdio.h>
#define N 200010
long long n;
long long smax=-30000,pmax,lmax;
long long v[N<<1];
long long d[N<<1],st=1,dr=1;
void citire()
{
	scanf("%lld",&n);
	int c;
	long long x;
	for(long long i=1; i<=n; i++)
	{
		scanf("%lld%d",&x,&c);
		if(c)
			v[i]=x;
		else
			v[i]=-x;
		v[i]+=v[i-1];
	}
	long long n1=n<<1;
	for(long long i=n+1; i<=n1; ++i)
		v[i]=v[i-1]+v[i-n]-v[i-n-1];
}
void rezolva()
{
	long long n1=n<<1;
	long long s=0,p=1,l=0;
	for(int i=1; i<=n1; ++i)
	{
		while(st<=dr && i-d[st]>n)
			++st;
		while(st<dr && v[d[dr]]>v[i])
			--dr;
		d[++dr]=i;
		s=v[i]-v[d[st]];
		p=d[st]+1 <=n ? d[st]+1 : d[st]+1-n;
		l=i-d[st];
		if(s>smax)
		{
			smax=s;
			pmax=p;
			lmax=l;
		}
		else
		if(s==smax)
		{
			if(pmax>p)
			{
				pmax=p;
				lmax=l;
			}
			else
			if(pmax==p)
			{
				if(lmax>l)
					lmax=l;
			}
		}
	}
}
int main()
{
	freopen("buline.in","r",stdin);
	freopen("buline.out","w",stdout);
	pmax=1<<30;
	smax=-pmax;
	citire();
	rezolva();
	//if(lmax==n)
	//	printf("%d 1 %d\n",smax,n);
	//else
	printf("%lld %lld %lld\n",smax,pmax,lmax);
	return 0;
}