Cod sursa(job #966163)

Utilizator proflaurianPanaete Adrian proflaurian Data 25 iunie 2013 14:12:28
Problema Tribute Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.55 kb
#include <cstdio>
#define N 50010
using namespace std;
int n,dx,dy,x,y,X[N],Y[N],bst(int*,int);
int main()
{
    freopen("tribute.in","r",stdin);
    freopen("tribute.out","w",stdout);
    for(scanf("%d%d%d",&n,&dx,&dy);n;n--){scanf("%d%d",&x,&y);X[x]++;Y[y]++;}
    printf("%d\n",bst(X,dx)+bst(Y,dy));
    return 0;
}
int bst(int *A,int d)
{
    int ret,act,HI,LO,R=0,L=0;
    for(ret=0,HI=50000;HI>d;HI--){R+=A[HI];ret+=A[HI]*(HI-d);}
    for(act=ret,LO=0,HI=d;HI<=50000;){L+=A[LO++];act+=L-R;R-=A[HI++];ret=ret<act?ret:act;}
    return ret;
}