Cod sursa(job #500313)

Utilizator silvia_the_bestSilvia Pripoae silvia_the_best Data 11 noiembrie 2010 21:06:27
Problema Tribute Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.05 kb
#include <cstdio>
#include <algorithm>

using namespace std;

#define FIN "tribute.in"
#define FOUT "tribute.out"

#define MAXN 50003

int N, Dx, Dy, R;

int A[MAXN], B[MAXN];

void solve(int V[], int L, int Mn, int Mx)
{
    int i, nl = V[Mn], nr, S, M;

    for (S = nr = 0, i = Mn + L + 1; i <= Mx; ++ i)
        S += V[i] * (i - Mn - L), nr += V[i];

    for (i = Mn + 1, M = S; i + L <= Mx; ++ i)
    {
        S += nl - nr;

        nl += V[i]; nr -= V[i + L];

        //printf("%d %d %d\n", nl, nr, S);

        M = min(M, S);
    }

    R += M;
}

int main()
{
    int i, x, y, MnA, MnB, MxA, MxB;

    freopen(FIN, "r", stdin);
    freopen(FOUT, "w", stdout);

    scanf("%d%d%d", &N, &Dx, &Dy);

    for (i = 1, MnA = MnB = MAXN, MxA = MxB = 0; i <= N; ++ i)
    {
        scanf("%d %d", &x, &y);

        ++ A[x], ++ B[y];

        MnA = min(x, MnA); MnB = min(y, MnB);
        MxA = max(x, MxA); MxB = max(y, MxB);
    }

    solve(A, Dx, MnA, MxA);
    solve(B, Dy, MnB, MxB);

    printf("%d\n", R);
}