Cod sursa(job #489426)

Utilizator stephy_yoyoIonescu Stefania stephy_yoyo Data 2 octombrie 2010 16:07:35
Problema Tribute Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.99 kb
# include <cstdio>

int x[50001],y[50001];

int main ()
{
	freopen ("tribute.in","r",stdin);
	freopen ("tribute.out","w",stdout);
	int a,minx=500003,miny=500003,maxx=-1,maxy=-1,n,dx,dy;
	scanf ("%d%d%d",&n,&dx,&dy);
	for (int i=1;i<=n;i++)
	{
		scanf("%d",&a);
		x[a]++;
		if (minx>a)
			minx=a;
		if (maxx<a)
			maxx=a;
		scanf("%d",&a);
		y[a]++;
		if (miny>a)
			miny=a;
		if (maxy<a)
			maxy=a;
	}
	int s1=0,s2=0,t1=0,t2=0,sx,sy;
	for (int i=minx+dx+1;i<=maxx;i++)
	{
		t2+=x[i];
		s2+=x[i]*(i-minx-dx);
	}
	sx=s2;
	for (minx++;minx<=(maxx-dx);minx++)
	{
		s1+=t1;
		t1+=x[minx-1];
		s1+=x[minx-1];
		s2-=t2;
		t2-=x[minx+dx];
		if ((s1+s2)<sx)
			sx=s1+s2;
	}
	s2=t2=0;
	for (int i=miny+dy+1;i<=maxy;i++)
	{
		t2+=y[i];
		s2+=y[i]*(i-miny-dy);
	}
	sy=s2;
	s1=t1=0;
	for (miny++;miny<=(maxy-dy);miny++)
	{
		s1+=t1;
		t1+=y[miny-1];
		s1+=y[miny-1];
		s2-=t2;
		t2-=y[miny+dy];
		if ((s1+s2)<sy)
			sy=s1+s2;
	}
	printf ("%d",sx+sy);
	return 0;
}