Cod sursa(job #640588)

Utilizator sebii_cSebastian Claici sebii_c Data 25 noiembrie 2011 23:44:08
Problema Tribute Scor 90
Compilator c Status done
Runda Arhiva de probleme Marime 1.07 kb
#include <stdio.h>
#include <string.h>
#define NMAX 50000

const int INF = 0x3f3f3f3f;
int x1[NMAX + 50], x2[NMAX + 50], yy1[NMAX + 50], y2[NMAX + 50];
int a[NMAX + 50], b[NMAX + 50];

int main()
{
	freopen("tribute.in", "r", stdin);
	freopen("tribute.out", "w", stdout);
	int n, dx, dy, i, x, y;
	scanf("%d %d %d", &n, &dx, &dy);
	for (i = 0; i < n; ++i) {
		scanf("%d %d", &x, &y);
		++a[x];
		++b[y];
	}
	
	int sum = a[0];
	for (i = 1; i <= NMAX; ++i) {
		x1[i] = x1[i - 1] + sum;
		sum += a[i];
	}
	
	sum = 0;
	for (i = NMAX; i >= 0; --i) {
		x2[i] = x2[i + 1] + sum;
		sum += a[i];
	}
	
	int minx = INF;
	for (i = 0; i <= NMAX; ++i) 
		if (x1[i] + x2[i + dx] < minx)
			minx = x1[i] + x2[i + dx];
	
	sum = b[0];
	for (i = 1; i <= NMAX; ++i) {
		yy1[i] = yy1[i - 1] + sum;
		sum += b[i];
	}
	
	sum = 0;
	for (i = NMAX; i >= 0; --i) {
		y2[i] = y2[i + 1] + sum;
		sum += b[i];
	}
	
	int miny = INF;
	for (i = 0; i <= NMAX; ++i)
		if (yy1[i] + y2[i + dy] < miny)
			miny = yy1[i] + y2[i + dy];
	
	printf("%d\n", minx + miny);
	return 0;
}