Cod sursa(job #1350109)

Utilizator retrogradLucian Bicsi retrograd Data 20 februarie 2015 17:48:00
Problema Tribute Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 kb
#include<fstream>
#include<algorithm>

using namespace std;
typedef int64_t var;

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

var X[100001], Y[100001];

int main() {
    var n, dx, dy, x, y;
    var px = 0, py = 0;
    var distx = 0;
    var disty = 0;

    fin>>n>>dx>>dy;
    for(var i=1; i<=n; i++) {
        fin>>x>>y;
        X[x] ++;
        if(x >= dx) {
            distx += x - dx;
            px ++;
        }
        Y[y] ++;
        if(y >= dy) {
            disty += y - dy;
            py ++;
        }
    }

    var points = px;
    var bestdistx = (1LL << 50);
    var left;

    var x1 = 0, x2 = dx;

    for(;x1 <= n;) {

        if(distx < bestdistx) {
            bestdistx = distx;
            left = x1;
        }

        points-=X[x1];
        points-=X[x2];
        distx -= points;
        x1++;
        x2++;
    }

    points = py;
    var bestdisty = (1LL << 50);
    var bottom;
    var y1 = 0, y2 = dy;

    for(;y1 <= n;) {

        if(disty < bestdisty) {
            bestdisty = disty;
            bottom = y1;
        }

        points-=Y[y1];
        points-=Y[y2];
        disty -= points;
        y1++;
        y2++;
    }

    fout<<bestdistx+bestdisty;
}