Cod sursa(job #1295019)

Utilizator RaduVisanRadu Visan RaduVisan Data 18 decembrie 2014 17:49:09
Problema Tribute Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.15 kb
#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;

const int NMAX = 50010;

int N, DX, DY, X[NMAX], Y[NMAX];
long long Cnt[NMAX], Sum[NMAX], Ans;

long long Solve(int V[NMAX], int D)
{
    for(int i = 0; i < NMAX; ++ i) Cnt[i] = Sum[i] = 0;

    for(int i = 1; i <= N; ++ i)
        Cnt[ V[i] ] ++, Sum[ V[i] ] += V[i];

    for(int i = 1; i < NMAX; ++ i)
    {
        Cnt[i] += Cnt[i - 1];
        Sum[i] += Sum[i - 1];
    }

    long long NowCost = (1LL << 62);
    for(int i = 0; i + D < NMAX; ++ i)
    {
        long long CntLeft = Cnt[i - 1], CntRight = Cnt[NMAX - 1] - Cnt[i + D];
        long long CurrentCost = 1LL * CntLeft * i - Sum[i - 1] + Sum[NMAX - 1] - Sum[i + D] - 1LL * CntRight * (i + D);
        NowCost = min(NowCost, CurrentCost);
    }
    return NowCost;
}

int main()
{
    freopen("tribute.in", "r", stdin);
    freopen("tribute.out", "w", stdout);

    scanf("%i %i %i", &N, &DX, &DY);
    for(int i = 1; i <= N; ++ i)
        scanf("%i %i", &X[i], &Y[i]);

    sort(X + 1, X + N + 1);
    sort(Y + 1, Y + N + 1);

    printf("%lld\n", Solve(X, DX) + Solve(Y, DY));
}