Cod sursa(job #30019)

Utilizator alextheroTandrau Alexandru alexthero Data 12 martie 2007 13:50:30
Problema Tribute Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.07 kb
#include <stdio.h>
#include <algorithm>

#define vmax 50005
#define nmax 50005
#define inf 2000000000

using namespace std;

int x[nmax],y[nmax],px[nmax];
int n,dx,dy,i;
int partx = inf,party = inf;

int main() {
	freopen("tribute.in","r",stdin);
	// freopen("tribute.out","w",stdout);

	scanf("%d%d%d",&n,&dx,&dy);
	
	int tot = 0;
	for(i = 1; i <= n; i++) {
		scanf("%d%d",&x[i],&y[i]);
		tot += x[i];
	}

	sort(x + 1,x + n + 1);
	for(i = 1; i <= n; i++) px[i] = px[i - 1] + x[i];

	int sx = 0,sy = 0;
	for(i = 0; i <= vmax; i++) {
		while(sy + 1 <= n && i + dx >= x[sy + 1]) sy++;
		while(sx + 1 <= n && i > x[sx + 1]) sx++;
		tot = (i * sx) - px[sx] + px[n] - px[sy] - (n - sy) * i - dx * (n -sy);
		partx = min(partx,tot);
	}

	sort(y + 1,y + n + 1);
	for(i = 1; i <= n; i++) px[i] = px[i - 1] + y[i];
	
	sx = 0,sy = 0;
	for(i = 0; i <= vmax; i++) {
		while(sy + 1 <= n && i + dy >= y[sy + 1]) sy++;
		while(sx + 1 <= n && i > y[sx + 1]) sx++;
		tot = (i * sx) - px[sx] + px[n] - px[sy] - (n - sy) * i - dx * (n -sy);
		party = min(party,tot);
	}

	printf("%d\n",partx + party);

	return 0;
}