Cod sursa(job #2242820)

Utilizator FunnyStockyMihnea Andreescu FunnyStocky Data 19 septembrie 2018 16:42:08
Problema Tribute Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.4 kb
#include <fstream>

using namespace std;

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

typedef long long ll;

const int N =  50000 + 5;

int n, dx, dy;

int x[N];
int y[N];

int f[N];

ll di1[N];
ll di2[N];

ll mi1 = (1LL << 60);
ll mi2 = (1LL << 60);

int main() {
        fin >> n >> dx >> dy;
        for (int i = 1; i <= n; i++) {
                fin >> x[i];
                fin >> y[i];
        }
        /// x :
        for (int i = 1; i <= n; i++) {
                f[x[i]]++;
        }
        int CntLeft = 0;
        for (int st = 0; st + dx < N; st++) {
                if (st > 0) {
                        CntLeft += f[st - 1];
                }
                int dr = st + dx;
                di1[st] += CntLeft;
                if (st > 0) {
                        di1[st] += di1[st - 1];
                }
        }
        int CntRight = 0;
        for (int dr = N - 1; dr >= dx; dr--) {
                if (dr + 1 < N) {
                        CntRight += f[dr + 1];
                }
                int st = dr - dx;
                di2[st] += CntRight;
                if (dr + 1 < N) {
                        di2[st] += di2[st + 1];
                }
        }
        for (int i = 0; i + dx < N; i++) {
                mi1 = min(mi1, di1[i] + di2[i]);
                di1[i] = 0;
                di2[i] = 0;
        }
        /// y :
        swap(dx, dy);
        for (int i = 0; i < N; i++) {
                f[i] = 0;
        }
        for (int i = 1; i <= n; i++) {
                swap(x[i], y[i]);
                f[x[i]]++;
        }
        CntLeft = 0;
        for (int st = 0; st + dx < N; st++) {
                if (st > 0) {
                        CntLeft += f[st - 1];
                }
                int dr = st + dx;
                di1[st] += CntLeft;
                if (st > 0) {
                        di1[st] += di1[st - 1];
                }
        }
        CntRight = 0;
        for (int dr = N - 1; dr >= dx; dr--) {
                if (dr + 1 < N) {
                        CntRight += f[dr + 1];
                }
                int st = dr - dx;
                di2[st] += CntRight;
                if (dr + 1 < N) {
                        di2[st] += di2[st + 1];
                }
        }
        for (int i = 0; i + dx < N; i++) {
                mi2 = min(mi2, di1[i] + di2[i]);
        }
        ll ans = mi1 + mi2;
        fout << ans << "\n";
        return 0;
}
/**

**/