Cod sursa(job #601569)

Utilizator luckyme91wiz kid luckyme91 Data 7 iulie 2011 00:22:30
Problema Tribute Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.74 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;
int n;
int dist_min (vector <int> X, int Dx)
{
	int i, Min = 0;
	for (i = Dx; i < X.size(); i++)
		Min +=  X[i] * (i - Dx);
	int dist = Min;
	for (i = 1; i < X.size(); i++)
		X[i] += X[i - 1];
	for (i = 1; i + Dx < X.size() ; i++)
	{
		dist += X[i - 1];
		dist -= n - X[i + Dx - 1];
		Min = min (dist, Min);
	}
	return Min;
}
	
int main () {

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

int dx, dy, i, x, y;
in >> n >> dx >> dy;

vector <int> X (n), Y (n);
for (i = 0; i < n; i++)
{
	in >> x >> y;
	if (x >= X.size())
		X.resize (x + 1);
	if (y >= Y.size())
		Y.resize (y + 1);
	X[x] ++;	
	Y[y] ++;
}
out << dist_min (X, dx) + dist_min (Y, dy);

return 0;
}