Cod sursa(job #1662490)

Utilizator lacraruraduRadu Matei Lacraru lacraruradu Data 24 martie 2016 19:54:06
Problema Tribute Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.32 kb
#include <fstream>

using namespace std;

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

#define N 50001

struct punct
{
    int x, y;
};

int n, dx, dy;
punct v[N];
int nrpx[N], nrpy[N];

inline long long minim(long long a, long long b)
{
    return a < b ? a : b;
}

int main()
{
    in >> n >> dx >> dy;
    for(int i = 1; i <= n; i++)
    {
        in >> v[i].x >> v[i].y;
        nrpx[v[i].x]++;
        nrpy[v[i].y]++;
    }

    int st = 0, dr = 0;
    long long dmin, dmin2, distanta = 0;
    for(int i = dx + 1; i <= 50000; i++)
    {
        dr += nrpx[i];
        distanta += (long long)(i - dx) * nrpx[i];

    }
    dmin = distanta;
    int lim = N - dx - 1;
    for(int i = 1; i <= lim; i++)
    {
        st += nrpx[i - 1];
        distanta += st - dr;
        dr -= nrpx[i + dx];
        dmin = minim(dmin, distanta);
    }
    st = 0, dr = 0, distanta = 0;
    for(int i = dy + 1; i <= 50000; i++)
    {
        dr += nrpy[i];
        distanta += (long long)(i - dy) * nrpy[i];
    }
    dmin2 = distanta;
    lim = N - dy - 1;
    for(int i = 1; i <= lim; i++)
    {
        st += nrpy[i - 1];
        distanta += st - dr;
        dr -= nrpy[i + dy];
        dmin2 = minim(dmin2, distanta);
    }
    out << (long long)dmin + dmin2 << '\n';
    return 0;
}