Cod sursa(job #123378)

Utilizator alex_mircescuAlex Mircescu alex_mircescu Data 15 ianuarie 2008 18:35:19
Problema Tribute Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.78 kb
#include <stdio.h>
#include <math.h>

#define MAX_V 50000

long n;
long find(long f[], long d) {
	long st = 0, dr = 0, cost = 0, ipr = 0;
	for (ipr = d + 1; ipr <= MAX_V; ++ipr) {
		dr += f[ipr];
		cost += (ipr - d) * f[ipr];
	}
	
	long cost_min = cost;
	
	for (ipr = 1; ipr + d <= MAX_V; ++ipr) {
		st += f[ipr - 1];
		cost += st - dr;
		dr -= f[ipr + d];
		if (cost < cost_min) {
			cost_min = cost;
		}
	}
	return cost_min;
}

long fx[MAX_V + 10], fy[MAX_V + 10], x, y, dx, dy;
int main() {
	long i;
	freopen("tribute.in", "r", stdin);
	freopen("tribute.out", "w", stdout);
	scanf("%ld %ld %ld", &n, &dx, &dy);
	for (i = 1; i <= n; ++i) {
		scanf("%ld %ld", &x, &y);
		++fx[x];
		++fy[y];
	}
	printf("%ld\n", find(fx, dx) + find(fy, dy));
	return 0;
}