Cod sursa(job #500284)

Utilizator silvia_the_bestSilvia Pripoae silvia_the_best Data 11 noiembrie 2010 20:36:16
Problema Tribute Scor 70
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 i, nl = V[V[N]], nr, S, M;

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

    for (i = V[N] + 1, M = S; i + L <= V[N + 1]; ++ 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;

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

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

    for (i = 1, A[N] = B[N] = MAXN, A[N + 1] = B[N + 1] = 0; i <= N; ++ i)
    {
        scanf("%d %d", &x, &y);

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

        A[N] = min(x, A[N]); B[N] = min(y, B[N]);
        A[N + 1] = max(x, A[N + 1]); B[N + 1] = max(y, B[N + 1]);
    }

    solve(A, Dx);
    solve(B, Dy);

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