Cod sursa(job #398099)

Utilizator iulia609fara nume iulia609 Data 17 februarie 2010 23:15:22
Problema Tribute Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.78 kb
#include <stdio.h>
#include <math.h>
using namespace std;
#define NMAX 50005

int N , x, y, Dx, Dy;
int X[NMAX + 10], Y[NMAX + 10];


int cauta(int V[], int d) 
{ int i, in, sf, C, min;
	
	in = sf = C = min = 0;
	
	for (i = d + 1; i <= NMAX; i++) 
	{
		sf += V[i];
		C += V[i] * (i - d);
	}
	
	min = C;
	
	for (i = 1; i + d <= NMAX; i++) 
	{
		in += V[i-1];
		
		C += in - sf;
		sf -= V[i + d];
		
		if (C < min) 
			min = C;
		
	}
	return min;
}


int main() 
{ int i;

	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, &y);
		X[x]++;
		Y[y]++;
	}
	
	int rez = cauta(X, Dx) + cauta(Y, Dy);
	
	printf("%d\n", rez);
	
	return 0;
}