Cod sursa(job #206148)

Utilizator devilkindSavin Tiberiu devilkind Data 4 septembrie 2008 22:14:11
Problema Tribute Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <stdio.h>
#include <algorithm>

using namespace std;

#define NMAX 50002

int X[NMAX],Y[NMAX];
int N,DX,DY;
int cst,mx,my;

int main()
{
	int i,p1,p2;

	freopen("tribute.in","r",stdin);
	freopen("tribute.out","w",stdout);

	scanf("%d %d %d",&N,&DX,&DY);
	
	for (i=1;i<=N;i++)
		scanf("%d %d",&X[i],&Y[i]);

	sort(X+1,X+N+1);
	sort(Y+1,Y+N+1);

	//fac treaba pe X
	cst=0;
	p1=0;p2=N+1;
	X[0]=0;X[N+1]=100002;
	for (i=1;i<=N;i++)
		if (X[i]>DX) {cst+=X[i]-DX;p2=min(p2,i);}

	mx=cst;
	for (i=1;i<=50000;i++)
	{
		cst=cst-(N-p2+1);	
		for (;X[p1]<i;p1++);
		for (;X[p2]<=i+DX;p2++);

		cst+=p1-1;
		mx=min(mx,cst);
	}
	//fac aceeasi treaba pe Y

	cst=0;
	p1=0;p2=N+1;
	Y[0]=0;Y[N+1]=100002;
	for (i=1;i<=N;i++)
		if (Y[i]>DY) {cst+=Y[i]-DY;p2=min(p2,i);}

	my=cst;
	for (i=1;i<=50000;i++)
	{
		cst=cst-(N-p2+1);
		
		for (;Y[p1]<i;p1++);
		for (;Y[p2]<=i+DY;p2++);

		cst+=p1-1;
		my=min(my,cst);
	}
	
	printf("%d ",mx+my);
	return 0;
}