Cod sursa(job #966166)

Utilizator proflaurianPanaete Adrian proflaurian Data 25 iunie 2013 14:16:26
Problema Tribute Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.59 kb
#include <cstdio>
#define N 50010
#define tip long long
using namespace std;
tip n,dx,dy,x,y,X[N],Y[N],bst(tip*,tip);
int main()
{
    freopen("tribute.in","r",stdin);
    freopen("tribute.out","w",stdout);
    for(scanf("%lld%lld%lld",&n,&dx,&dy);n;n--){scanf("%lld%lld",&x,&y);X[x]++;Y[y]++;}
    printf("%lld\n",bst(X,dx)+bst(Y,dy));
    return 0;
}
tip bst(tip *A,tip d)
{
    tip 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;
}