Cod sursa(job #997875)

Utilizator poptibiPop Tiberiu poptibi Data 15 septembrie 2013 00:15:42
Problema Tribute Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.1 kb
#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;

const int NMAX = 50005, INF = 0x3f3f3f3f;

int N, DX, DY, FreqX[NMAX + 5], FreqY[NMAX + 5], X[NMAX], Y[NMAX];
int Sum[NMAX + 5], Left[NMAX + 5], Right[NMAX + 5];

int Solve(int V[NMAX], int Empty)
{
    for(int i = 0; i < NMAX; ++ i) Left[i] = Right[i] = Sum[i] = 0;

    for(int i = 0; i < NMAX; ++ i)
    {
        Left[i] = Left[i - 1] + Sum[i - 1];
        Sum[i] = Sum[i - 1] + V[i];
    }
    for(int i = NMAX - 1; i >= 0; -- i)
    {
        Right[i] = Right[i + 1] + Sum[i + 1];
        Sum[i] = Sum[i + 1] + V[i];
    }

    int Ans = INF;
    for(int i = 0; i + Empty < NMAX; ++ i)
        Ans = min(Ans, Left[i] + Right[i + Empty]);
    return Ans;
}

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]);
        FreqX[X[i]] ++;
        FreqY[Y[i]] ++;
    }

    printf("%i\n", Solve(FreqX, DX) + Solve(FreqY, DY));
    return 0;
}