Cod sursa(job #1240551)

Utilizator killer301Ioan Andrei Nicolae killer301 Data 11 octombrie 2014 16:41:40
Problema Tribute Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.56 kb
/*#include <cstdio>
#include <vector>

using namespace std;

const int nmax=50005;
int n;
int v[2][nmax];

int d1(int k, int dx, int xmax)
{
	int s=0, min=0, posmin=0, l=0, r=0;
	for(int i=xmax;i>=dx;i--)
	{
		s+=v[k][i]*(i-dx+1);
		r+=v[k][i];
	}
	min=s;
	for(int i=1;i<=xmax;i++)
	{
		l+=v[k][i-1];
		if(i+dx<=xmax)r-=v[k][i+dx-1];
		s+=l-r;
		if(s<min)
		{
			min=s;
			posmin=i;
		}
	}
	return min;
}

int main()
{
    freopen("tribute.in", "r", stdin);
    freopen("tribute.out", "w", stdout);
    int dx, dy;
    int xmax=-1, ymax=-1;
    scanf("%d%d%d", &n, &dx, &dy);
    for(int i=0;i<n;i++)
	{
		int x, y;
		scanf("%d%d", &x, &y);
		if(x>xmax)xmax=x;
		if(y>ymax)ymax=y;
		v[0][x]++;
		v[1][y]++;
	}
	printf("%d\n", d1(0, dx, xmax)+d1(1, dy, ymax));
    return 0;
}
*/
#include <cstdio>

using namespace std;

const int nmax=50005;
int n;
int v[2][nmax];

int d1(int k, int dx, int xmax)
{
	int l=0, r=0, s=0, min=0;
	for(int i=xmax;i>dx;i--)
	{
		r+=v[k][i];
		s+=v[k][i]*(i-dx);
	}
	min=s;
	for(int i=1;i<=xmax;i++)
	{
		l+=v[k][i-1];
		s+=l-r;
		if(i+dx<=xmax)r-=v[k][i+dx];
		if(s<min)min=s;
	}
	return min;
}

int main()
{
    freopen("tribute.in", "r", stdin);
    freopen("tribute.out", "w", stdout);
    int dx, dy;
    int xmax=-1, ymax=-1;
    scanf("%d%d%d", &n, &dx, &dy);
    for(int i=0;i<n;i++)
	{
		int x, y;
		scanf("%d%d", &x, &y);
		if(x>xmax)xmax=x;
		if(y>ymax)ymax=y;
		v[0][x]++;
		v[1][y]++;
	}
	printf("%d\n", d1(0, dx, xmax)+d1(1, dy, ymax));
    return 0;
}