Cod sursa(job #2294542)

Utilizator Alex_BubBuburuzan Alexandru Alex_Bub Data 2 decembrie 2018 15:47:06
Problema Tribute Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.38 kb
#include <bits/stdc++.h>

using namespace std;

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

const int NMax = 50001;

struct {int sd, ds, nr;} X[NMax + 5], Y[NMax + 5];

int N, dx, dy, x, y;///DP[i] este suma minima pe x/y daca dreapta se afla de la i la i + dx/dy

int SolveMinX()
{
    int nr = 0;

    for(int i = 0; i <= NMax; i++)
        X[i].sd = X[i - 1].sd + nr, nr += X[i].nr;

    nr = 0;
    for(int i = NMax; i >= 0; i--)
        X[i].ds = X[i + 1].ds + nr, nr += X[i].nr;

    int mini = X[0].sd + X[dx].ds;

    for(int i = 1; i <= NMax; i++) {
        ///DP[i] = X[i].sd + X[i + dx].ds;
        mini = min(X[i].sd + X[i + dx].ds, mini);
    }

    return mini;
}

int SolveMinY()
{
    int nr = 0;

    for(int i = 0; i <= NMax; i++)
        Y[i].sd = Y[i - 1].sd + nr, nr += Y[i].nr;

    nr = 0;
    for(int i = NMax; i >= 0; i--)
        Y[i].ds = Y[i + 1].ds + nr, nr += Y[i].nr;

    int mini = Y[0].sd + Y[dy].ds;

    for(int i = 1; i <= NMax; i++) {
        ///DP[i] = Y[i].sd + Y[i + dy].ds;
        mini = min(Y[i].sd + Y[i + dy].ds, mini);
    }

    return mini;
}

int main()
{
    fin >> N >> dx >> dy;

    for(int i = 0; i < N; i++) {
        fin >> x >> y;
        X[x].nr++, Y[y].nr++;
    }

    fout << SolveMinX() + SolveMinY() << '\n';

    fin.close();
    fout.close();

    return 0;
}