Cod sursa(job #119977)

Utilizator sealTudose Vlad seal Data 3 ianuarie 2008 19:48:02
Problema Tribute Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.89 kb
#include<stdio.h>
#define Nm (1<<16)
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
int X[Nm],Y[Nm],dx,dy,mx,my;

void read()
{
    int n,x,y;
    
    freopen("tribute.in","r",stdin);
    scanf("%d%d%d",&n,&dx,&dy);
    while(n--)
    {
        scanf("%d%d",&x,&y);
        ++X[x]; ++Y[y];
        mx=max(mx,x);
        my=max(my,y);
    }
}

unsigned dist(int X[], int dx, int mx)
{
    if(mx<=dx)
        return 0;
        
    int i,l=0,r=0;
    unsigned d=0,ans;

    for(i=dx+1;i<=mx;++i)
        r+=X[i], d+=X[i]*(i-dx);
    ans=d;
    for(i=1;i<=mx-dx;++i)
    {
        l+=X[i-1]; d+=l;
        d-=r; r-=X[i+dx];
        ans=min(ans,d);
    }
    return ans;
}

void write()
{
    freopen("tribute.out","w",stdout);
    printf("%u\n",dist(X,dx,mx)+dist(Y,dy,my));
}

int main()
{
    read();
    write();
    return 0;
}