Cod sursa(job #2451455)

Utilizator ZanoxNonea Victor Zanox Data 26 august 2019 19:43:22
Problema Tribute Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.84 kb
#include <fstream>
#include <iostream>
#include <climits>
#include <cstring>

using namespace std;


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

#define RANGE 50000

int d;
int spot[RANGE + 1];
int distLeft[RANGE + 1], distRight[RANGE + 1];
int solSpot, solDist;

#define DIST_LEFT(i) (((i) >= 0 && (i) <= RANGE) ? distLeft[i] : 0)
#define DIST_RIGHT(i) (((i) >= 0 && (i) <= RANGE) ? distRight[i] : 0)

void runRoutine();

int main() {
    int n, dx, dy;
    fin>>n>>dx>>dy;

    int* vx = new int[RANGE + 1];
    memset(vx, 0, sizeof(int) * (RANGE + 1));
    int* vy = new int[RANGE + 1];
    memset(vy, 0, sizeof(int) * (RANGE + 1));

    for (int i = 0; i < n; i++) {
        int x, y;
        fin>>x>>y;

        vx[x]++;
        vy[y]++;
    }


    //initialize for x
    d = dx;
    memcpy(spot, vx, sizeof(int) * (RANGE + 1));

    runRoutine();

    int distX = solDist;
    //cout<<"Spot: "<<solSpot<<"\nDist: "<<solDist<<'\n';


    //initialize for y
    d = dy;
    memcpy(spot, vy, sizeof(int) * (RANGE + 1));

    runRoutine();

    int distY = solDist;
    //cout<<"Spot: "<<solSpot<<"\nDist: "<<solDist<<'\n';

    fout<<distX + distY<<'\n';
}

void runRoutine() {
    //populate distLeft
    for (int i = 0, prez = 0, accum = 0; i < RANGE + 1; i++) {
        accum += prez;
        distLeft[i] = accum;

        if (spot[i]) prez+= spot[i];
    }

    //populate distRight
    for (int i = RANGE, prez = 0, accum = 0; i >= 0; i--) {
        accum += prez;
        distRight[i] = accum;

        if (spot[i]) prez+= spot[i];
    }

    //get min total
    solSpot = -1, solDist = INT_MAX;

    for (int i = 0; i < RANGE + 1; i++)
    if (solDist > DIST_LEFT(i) + DIST_RIGHT(i + d)) {
        solDist = DIST_LEFT(i) + DIST_RIGHT(i + d);
        solSpot = i;
    }
}