Cod sursa(job #966210)

Utilizator proflaurianPanaete Adrian proflaurian Data 25 iunie 2013 15:03:08
Problema Tribute Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.85 kb
#include <cstdio>
#include<algorithm>
#define N 50010
#define tip long long
using namespace std;
tip n,dx,dy,x,y,X[N],Y[N],ST[N],DR[N],CS[N],CD[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,i,st,dr;
    ST[0]=0;
    CS[0]=A[0];
    for(i=1;i<=50001;i++)
    {
        CS[i]=CS[i-1]+A[i];
        ST[i]=ST[i-1]+CS[i-1];
    }
    DR[50001]=0;CD[50001]=0;
    for(i=50000;i>=0;i--)
    {
        CD[i]=CD[i+1]+A[i];
        DR[i]=DR[i+1]+CD[i+1];
    }
    ret=DR[d];
    for(st=1,dr=d+1;dr<=50001;st++,dr++)
        ret=min(ret,ST[st]+DR[dr]);
    return ret;
}