Cod sursa(job #1135266)

Utilizator tudorv96Tudor Varan tudorv96 Data 7 martie 2014 16:36:25
Problema Tribute Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.62 kb
#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);
}