Cod sursa(job #672765)

Utilizator vlad2901Vlad Berindei vlad2901 Data 3 februarie 2012 01:49:12
Problema Tribute Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.39 kb
#include <cstdio>
#include <vector>

#define NMAX 50001

int cx[NMAX+1], cy[NMAX+1];
int N, DX, DY;

int main()
{
    int sumxa[NMAX+1], sumxd[NMAX+1], sumya[NMAX+1], sumyd[NMAX+1];

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

    scanf("%d %d %d", &N, &DX, &DY);

    for(int i=0;i<N;++i)
    {
        int x, y;
        scanf("%d %d", &x, &y);
        cx[x]++;
        cy[y]++;
    }

    int valxa = cx[0], valya = cy[0], valxd = cx[NMAX], valyd = cy[NMAX];
    sumxa[0] = valxa;
    sumya[0] = valya;
    sumxd[NMAX] = valxd;
    sumyd[NMAX] = valyd;


    for(int i=1;i<=NMAX;++i)
    {
        valxa += cx[i];
        valya += cy[i];

        valxd += cx[NMAX-i];
        valyd += cy[NMAX-i];

        sumxa[i] = sumxa[i-1] + valxa;
        sumya[i] = sumya[i-1] + valya;

        sumxd[NMAX-i] = sumxd[NMAX-i+1] + valxd;
        sumyd[NMAX-i] = sumyd[NMAX-i+1] + valyd;
    }

    long long minx = (long long)NMAX * NMAX;
    long long miny = (long long)NMAX * NMAX;

    for(int i=0;i<NMAX;++i)
    {
        if(i<NMAX-DX && sumxa[i-1] + sumxd[i+DX+1] < minx)
        {
            minx = sumxa[i-1] + sumxd[i+DX+1];
        }

        if(i<NMAX-DY && sumya[i-1] + sumyd[i+DY+1] < miny)
        {
            miny = sumya[i-1] + sumyd[i+DY+1];
        }
    }

    printf("%d", minx + miny);


    return 0;
}