Cod sursa(job #351370)

Utilizator jeanFMI - Petcu Ion Cristian jean Data 27 septembrie 2009 20:39:21
Problema Tribute Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.85 kb
#include<cstdio>
#define max 50010

int n,x,y,i,pd,ps,pup,pdwn,px[max],py[max],xmax,ymax,st,dr,sus,jos;
long long distx,disty,bestx,besty;

int main()
{
	freopen("tribute.in","r",stdin);
	freopen("tribute.out","w",stdout);
	
	scanf("%d %d %d",&n,&dr,&sus);
	
	for(i=1;i<=n;i++)
	{
		scanf("%d %d",&x,&y);
		
		if(x>xmax) xmax=x;
		if(y>ymax) ymax=y;
		
		px[x]++;
		py[y]++;
		
		if(x>dr)  {pd++;  distx+=x-dr;} 
		if(y>sus) {pup++; disty+=y-sus;} 
	}
bestx=distx;
besty=disty;
	for(st=0; dr<xmax; st++,dr++)
	{
		ps+=px[st];
		distx+=ps;
		
		distx-=pd;		
		pd-=px[dr+1];
				
		if(distx<bestx) bestx=distx;
	}
	
	for(jos=0; sus<ymax; jos++,sus++)
	{
		pdwn+=py[jos];
		disty+=pdwn;		
		
		disty-=pup;		
		pup-=py[sus+1];		
		
		if(disty<besty) besty=disty;
	}
	
printf("%lld",bestx+besty);
return 0;
}