Cod sursa(job #1605998)

Utilizator kassay_akosKassay Akos kassay_akos Data 19 februarie 2016 17:58:39
Problema Tribute Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.22 kb
#include <iostream>
#include <fstream>
#include <string.h>
//#include <vector>
//#include <queue>
//#include <algorithm>

using namespace std;
const int nmax = 50001;
int x[nmax], y[nmax];		// x[p] - the number of p numbers
int dleft[nmax], dright[nmax];
int n, dx, dy;

inline long long int min(long long int a, long long int b) {
	if (a > b) return b;
	else return a;
}

long long int dis(int r[], int len) {
	// distantele de la stanga
	int next = r[0];
	dleft[0] = 0;
	for (int i = 1; i < nmax; i++) {
		dleft[i] = dleft[i-1] + next;
		next += r[i];
	}

	// distantele de la dreapta
	next = 0;
	for (int i = nmax - 2; i >= 0; i--){
		dright[i] = dright[i+1] + next;
		next += r[i];
	}

	// calcularea minimului
	long long int minim = 0x7FFFFFFFFFFFFFFF;
	for (int i = 0; i < nmax - len; i++) {
		minim = min(minim, dleft[i] + dright[i + len]);
	}
	return minim;
}

int main(){
	
	freopen("tribute.in", "r", stdin);
	freopen("tribute.out", "w", stdout);
	
	scanf("%d %d %d", &n, &dx, &dy);

	int xx = 0, yy = 0;
	for (int i = 0; i < n; i++) {
		scanf("%d %d", &xx, &yy);
		x[xx]++;
		y[yy]++;
	}

	printf("%lld", (dis(x,dx) + dis(y,dy)) );
	
	fclose(stdin);
	fclose(stdout);
	
	return 0;
}