Cod sursa(job #459359)

Utilizator antoanelaAntoanela Siminiuc antoanela Data 29 mai 2010 13:48:09
Problema Tribute Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.75 kb
#include <cstdio>
#define l 50000
#define nmax 50010

int x[nmax], y[nmax], a[nmax], b[nmax], t[nmax], n, dx, dy;

int solve()
{
	int i;
	for (i=0; i<=l; i++) a[i]=b[i]=0;
	int s=0;
	for (i=1; i<=l; i++)
	{
		s+=t[i-1];
		a[i]=a[i-1]+s;
	}
	s=0;
	for (i=l-1; i>=0; i--)
	{
		s+=t[i+1];
		b[i]=b[i+1]+s;
	}
	int m=nmax;
	for (i=0; i+dx<=l; i++) 
	{
		a[i]+=b[i+dx];
		if (a[i]<m) m=a[i];
	}
	return m;
}

int main()
{
	freopen("tribute.in","r",stdin);
	freopen("tribute.out","w",stdout);
	scanf("%d %d %d",&n,&dx,&dy);
	int i;
	for (i=1; i<=n; i++) 
	{
		scanf("%d %d",&x[i],&y[i]);
		t[x[i]]++;
	}
	int sol=solve();
	for (i=0; i<=l; i++) t[i]=0;
	for (i=1; i<=n; i++) t[y[i]]++;
	dx=dy;
	sol+=solve();
	printf("%d",sol);
}