Cod sursa(job #431634)

Utilizator yoyo_mayaionescu mircea yoyo_maya Data 1 aprilie 2010 11:23:01
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.86 kb
#include<stdio.h>
int x[400001], d[400001],n,i,a,b,p,u,max,q,q1,qmax,q1max;
FILE *f,*g;
int main(){
	f=fopen("buline.in","r");
	g=fopen("buline.out","w");
	fscanf(f,"%d",&n);
	for(i=1;i<=n;i++){
		fscanf(f,"%d%d",&a,&b);
		if(b==0)
			x[i]=-a;
		else
			x[i]=a;
		x[n+i]=x[i];
	}
	for(i=1;i<=2*n;i++)
		x[i]=x[i-1]+x[i];
	
p=u=1;
d[p]=0;

for(i=1;i<=2*n;i++)
{
	while(i-d[p]>=n&&p<=u)
		p++; 
	if(p<=u){
		if(i<=n){
			   q=d[p]+1;
			   q1=i-d[p];}
		  else{
			  q=d[p]+1;
			 q1=i-d[p];
		  }
	if(x[i]-x[d[p]]>max){
		  max=x[i]-x[d[p]];
		  qmax=q;
		  q1max=q1;
	}
	/*else
		if(x[i]-x[d[p]]==max){
			if(q<qmax)
				 qmax=q;
			else
				if(q==qmax)
					if(q1<q1max)
						q1max=q1;
		}*/
	
	}
	
	while(x[i]<=x[d[u]]&&u>=p)
		 u--;
	
	
	u++;
	d[u]=i;
}
fprintf(g,"%d %d %d",max,qmax,q1max);
return 0;
}