Pagini recente » Cod sursa (job #1638138) | Cod sursa (job #962922) | Cod sursa (job #1030257) | Cod sursa (job #3148604) | Cod sursa (job #1135266)
#include <fstream>
#include <vector>
using namespace std;
ifstream fin ("tribute.in");
ofstream fout ("tribute.out");
const int CMAX = 5e4 + 5;
int n, dx, dy, sp_x[CMAX], sp_y[CMAX];
vector <int> X, Y;
int bs_low(vector <int> &v, int x) {
int poz = v.size();
for (int step = (1 << 16); step; step >>= 1)
if (poz - step >= 0 && v[poz - step] > x)
poz -= step;
return poz;
}
int bs_high(vector <int> &v, int x) {
int poz = -1;
for (int step = (1 << 16); step; step >>= 1)
if (poz + step < v.size() && v[poz + step] <= x)
poz += step;
return poz + 1;
}
int best(int *s, int dist, vector <int> &v) {
int MIN = 1e9;
for (int i = v[0]; i <= v.back(); ++i) {
int d_crt = 0, k = bs_high(v, i-1);
d_crt = k * i - (i ? s[i-1] : 0);
k = bs_low(v, i + dist);
d_crt += s[v.back()] - (n - k) * (i + dist) - s[v[k - 1]];
MIN = min(MIN, d_crt);
}
return MIN;
}
int main() {
fin >> n >> dx >> dy;
for (int x, y, i = 0; i < n; ++i) {
fin >> x >> y;
sp_x[x] += x;
sp_y[y] += y;
if (!x)
X.push_back (x);
if (!y)
Y.push_back (y);
}
for (int i = 1; i < CMAX; ++i) {
for (int j = 0; j < sp_x[i]; j += i)
X.push_back (i);
for (int j = 0; j < sp_y[i]; j += i)
Y.push_back (i);
}
for (int i = min(X[0], Y[0]); i <= max(X.back(), Y.back()); ++i) {
sp_x[i] += sp_x[i-1];
sp_y[i] += sp_y[i-1];
}
fout << best(sp_x, dx, X) + best(sp_y, dy, Y);
}