Cod sursa(job #2309848)

Utilizator alex12_roGuster Alexandru alex12_ro Data 29 decembrie 2018 22:16:27
Problema Tribute Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.8 kb
#include <fstream>
#include <algorithm>

using namespace std;

ifstream f("tribute.in");
ofstream g("tribute.out");

const int N = 50005;
int n, i, j, x[N], y[N];
int cntx[N], cnty[N], dx, dy;

int calc(int v[], int cnt[], int d) {
    int i, sum = 0, nrdr = 0, nrst = 0;
    sort(v+1, v+n+1);
    for (i = 1; i <= n; i++) {
        cnt[v[i]]++;
        if (v[i] > d) {
            sum += v[i] - d;
            nrdr++;
        }
    }
    int minim = sum;
    for (i = 1; i+d <= 50000; i++) {
        nrst += cnt[i-1];
        sum += nrst - nrdr;
        nrdr -= cnt[i+d];
        if (sum < minim) minim = sum;
    }
    return minim;
}

int main() {
    f >> n >> dx >> dy;
    for (i = 1; i <= n; i++)
        f >> x[i] >> y[i];

    g << calc(x, cntx, dx) + calc(y, cnty, dy);
}