Pagini recente » Cod sursa (job #2891671) | Cod sursa (job #1685599) | Cod sursa (job #180526) | Cod sursa (job #2023022) | Cod sursa (job #970744)
Cod sursa(job #970744)
#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;
}