Cod sursa(job #444574)

Utilizator jeanFMI - Petcu Ion Cristian jean Data 20 aprilie 2010 20:25:10
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.72 kb
#include<stdio.h>
#define Nmax 200010
#define Inf 1ll<<60

long long sum[Nmax<<1],best;
int dq[Nmax<<1],i,p,u,n,L,P,semn,nn;

int main()
{
	freopen("buline.in","r",stdin);
	freopen("buline.out","w",stdout);
	
	scanf("%d",&n);
	
	for(i=1;i<=n;i++)
	{
		scanf("%d %d",&sum[i],&semn);
		if(!semn) sum[i]=-sum[i];
		sum[i+n]=sum[i];
	}
	
	nn=n<<1;
	
	for(i=1;i<=nn;i++)
		sum[i]+=sum[i-1];
	
	dq[1]=1; p=u=1;
	best=-Inf;
	
	for(i=2;i<=nn;i++)
	{
		while( i-dq[p]+1 > n && p<=u ) p++;
		
		if( sum[i]-sum[dq[p]] > best )
		{
			best=sum[i]-sum[dq[p]];
			P=dq[p]+1;
			L=i-dq[p];
		}
		
		while( sum[i]<sum[dq[u]] && p<=u) u--;
		dq[++u]=i;
	}
	
	printf("%lld %d %d",best,P,L);
	return 0;
}