Cod sursa(job #212465)

Utilizator mihai_floreaFlorea Mihai Alexandru mihai_florea Data 5 octombrie 2008 16:47:03
Problema Tribute Scor 10
Compilator c Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <stdio.h>
#define NMAX 50005
int N,DX,DY,x[NMAX],y[NMAX],nr[NMAX],sol;
void sort(int *v,int N){
     int i,j,m=0;
     for (i=0;i<NMAX;++i) nr[i]=0;
     for (i=1;i<=N;++i) nr[v[i]]++;
     for (i=0;i<NMAX;++i)
       for (j=1;j<=nr[i];++j)
        v[++m]=i;
     }
int solve(int v[NMAX],int L){
     int i,j,p,u,d=0,r;
     for (i=0;i<NMAX;++i) nr[i]=0;
     for (i=1;i<=N;++i) nr[v[i]]++;
     i=1;
     while (v[i]<=v[1]+L && i<=N) ++i;
     for (j=i;j<=N;++j) d+=(v[j]-v[1]-L);
     p=0;u=N-i+1;r=d;
     for (i=v[1]+1;i<=v[N]-L;++i){
         p+=nr[i-1];
         d+=(p-u);
         u-=nr[i+L];
         if (d<r) r=d;
         }
     return r;
     }
int main(){
    int i;
    freopen("tribute.in","r",stdin);
    freopen("tribute.out","w",stdout);
    scanf("%d %d %d",&N,&DX,&DY);
    for (i=1;i<=N;++i) scanf("%d %d",&x[i],&y[i]);
    sort(x,N);
    sort(y,N);
    sol+=solve(x,DX);
    sol+=solve(y,DY);
    printf("%d",sol);
    return sol;
}