Cod sursa(job #212459)

Utilizator mihai_floreaFlorea Mihai Alexandru mihai_florea Data 5 octombrie 2008 16:38:28
Problema Tribute Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.84 kb
#include <cstdio>
#include <algorithm>
using namespace std;
const int NMAX=50005;
int N,DX,DY,x[NMAX],y[NMAX],nr[NMAX],sol;
int solve(int v[NMAX],int L){
     int i,j,p,u,d=0,r;
     for (i=0;i<v[N];++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+1,x+N+1);
    sort(y+1,y+N+1);
    sol+=solve(x,DX);
    sol+=solve(y,DY);
    printf("%d",sol);
    return sol;
}