Cod sursa(job #820906)

Utilizator deneoAdrian Craciun deneo Data 21 noiembrie 2012 12:51:09
Problema Tribute Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <fstream>
#include <cstring>
#include <iostream>
using namespace std;

ifstream fin("tribute.in");
ofstream fout("tribute.out");

#define MAXDIM 51000
#define inf 1 << 30

int solve (int P[MAXDIM + 10], int dist, int N) {
	int sum[MAXDIM + 10], num[MAXDIM + 10], best = inf;
	
	memset (sum, 0, sizeof(sum));
	memset (num, 0, sizeof(num));
	
	for (int i = 1; i <= N; ++i) {
		sum[P[i]] += P[i];
		num[P[i]] += 1;
	}
	
	for (int i = 0; i <= MAXDIM; ++i) {
		sum[i] += sum[i - 1];
		num[i] += num[i - 1];
	}
	
	for (int i = 0; i <= MAXDIM - dist; ++i) {
		int now = 0;
		now += sum[MAXDIM] - sum[i + dist] - (i + dist) * (num[MAXDIM] - num[i + dist]);
		if (i != 0) now += i * num[i - 1] - sum[i - 1];
		if (now < best)
			best = now;
	}
	return best;
}

int main () {
	
	int DX, DY, N;
	int P[3][MAXDIM + 10];
	
	fin >> N >> DX >> DY;
	
	for (int i = 1; i <= N; ++i) 
		fin >> P[1][i] >> P[2][i];
	
	fout << solve (P[1], DX, N) + solve (P[2], DY, N);
	
	return 0;
}