Cod sursa(job #643262)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 3 decembrie 2011 12:32:33
Problema Tribute Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.51 kb
/*#include <cstdio>

#define NMax 50005

using namespace std;

int N, DX, DY, PX[NMax+5], PY[NMax+5];

inline int Min (int a, int b)
{
    if (a<b)
    {
        return a;
    }
    return b;
}

inline int Solve (int V[], int D)
{
    int S, CurrentS=0;
    for (int i=D; i<NMax; ++i)
    {
        CurrentS+=((i-D)*V[i]);
    }
    S=CurrentS;
    for (int i=1; i<NMax; ++i)
    {
        V[i]+=V[i-1];
    }
    for (int i=1; i+D<NMax; ++i)
    {
        CurrentS+=V[i-1];
        CurrentS-=(N-V[i+D-1]);
        S=Min (S, CurrentS);
    }
    return S;
}

void Read ()
{
    freopen ("tribute.in", "r", stdin);
    scanf ("%d", &N);
    for (int i=1; i<=N; ++i)
    {
        int X, Y;
        scanf ("%d %d", &X, &Y);
        ++PX[X];
        ++PY[Y];
    }
}

void Print ()
{
    freopen ("tribute.out", "w", stdout);
    printf ("%d\n", Solve (PX, DX)+Solve (PY, DY));
}

int main()
{
    Read ();
    Print ();
    return 0;
}
*/

#include <fstream>
using namespace std;

const int N=50005;
int X[N+5],Y[N+5],dX,dY,n;

ifstream in("tribute.in");
ofstream out("tribute.out");

int det(int v[],int D)
{
	int i,M,dist=0;
	for (i=D;i<N;i++)
		dist+=v[i]*(i-D);
	M=dist;
	for (i=1;i<N;i++)
		v[i]+=v[i-1];
	for (i=1;i+D<N;i++)
	{
		dist+=v[i-1];
		dist-=n-v[i+D-1];
		M=min(dist,M);
	}
	return M;
}

int main()
{
	int i,x,y;
	in>>n>>dX>>dY;
	for (i=1;i<=n;i++)
	{
		in>>x>>y;
		X[x]++;
		Y[y]++;
	}
	out<<det(X,dX)+det(Y,dY)<<"\n";
	return 0;
}