Cod sursa(job #1335340)

Utilizator akaprosAna Kapros akapros Data 5 februarie 2015 14:00:10
Problema Tribute Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.97 kb
#include<cstdio>
#include<algorithm>
#define Nmax 50005
#define Inf 2000000000
using namespace std;
int n,i,j,p,q,nr,dx,dy;
struct nod
{
    int x;
    int y;
}v[Nmax];
int a[Nmax],b[Nmax];
int sx1[Nmax],sx2[Nmax],sy1[Nmax],sy2[Nmax];
int sol(int s1[Nmax],int s2[Nmax],int d)
{
    int i,j,min=Inf;
    int a=0,b=0;
    for (i=0;i+d<=Nmax;i++)
    {
        a=s1[i]*i-s2[i];
        b=s2[Nmax]-s2[i+d]-(s1[Nmax]-s1[i+d])*(i+d);
        if (a+b<min) min=a+b;
    }
    return min;
}
int main()
{
    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",&v[i].x,&v[i].y);
        ++a[v[i].x];
        ++b[v[i].y];
    }
    for (i=0;i<=Nmax;i++)
    {
        sx1[i]=sx1[i-1]+a[i];
        sx2[i]=sx2[i-1]+a[i]*i;
        sy1[i]=sy1[i-1]+b[i];
        sy2[i]=sy2[i-1]+b[i]*i;
    }
    printf("%d",sol(sx1,sx2,dx)+sol(sy1,sy2,dy));
    return 0;
}