Cod sursa(job #970744)

Utilizator toranagahVlad Badelita toranagah Data 7 iulie 2013 18:18:25
Problema Tribute Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.12 kb
#include <algorithm>
#include <fstream>
#include <iostream>
#include <vector>
using namespace std;

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

const int MAX_N = 50001;
const int INF = 1 << 30;

int sweep(vector<int> &points, int length);

int main() {
	int n, dx, dy;
	fin >> n >> dx >> dy;
	vector<int> x(n);
	vector<int> y(n);

	for (int i = 0; i < n; ++i) {
		fin >> x[i] >> y[i];
	}

	fout << sweep(x, dx) + sweep(y, dy);
	return 0;
}

int sweep(vector<int> &points, int length) {
  vector<int> distance_sums(MAX_N + 1, 0);
	vector<int> num_points(MAX_N + 1, 0);

	for (auto point : points) {
		distance_sums[point] += point;
		num_points[point] += 1;
	}

	for (int i = 1; i <= MAX_N; ++i) {
		distance_sums[i] += distance_sums[i - 1];
		num_points[i] += num_points[i - 1];
	}

	int result = INF;
	for (int i = 0; i + length < MAX_N; ++i) {
		int end_point = i + length, cost; 
		cost = (distance_sums[MAX_N] - distance_sums[end_point]) -
					 end_point * (num_points[MAX_N] - num_points[end_point]);
		if (i > 0) {
			cost += i * (num_points[i - 1]) - distance_sums[i - 1];
		}
		result = min(result, cost);
	}
	return result;
}