Cod sursa(job #554062)

Utilizator loginLogin Iustin Anca login Data 14 martie 2011 16:09:40
Problema Tribute Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.78 kb
# include <fstream>
# define DIM 50003
# define INF 2147000000
using namespace std;
int n, dx, dy, x[DIM], y[DIM], st[DIM], dr[DIM], sol, X1, X0=INF, Y1, Y0=INF;

void read ()
{
	ifstream fin ("tribute.in");
	fin>>n>>dx>>dy;
	int t;
	for(int i=1;i<=n;++i)
	{
		fin>>t;++x[t+1];
		if (t+1<X0)X0=t+1;
		if (t+1>X1)X1=t+1;
		fin>>t;++y[t+1];
		if (t+1<Y0)Y0=t+1;
		if (t+1>Y1)Y1=t+1;
	}
}

int f (int v[], int d, int a, int b)
{
	st[a-1]=0;
	int i, el=0, r=INF;
	for(i=a;i<=b;++i)
	{
		st[i]=st[i-1]+el;
		el+=v[i];
	}
	el=0;
	dr[b+1]=0;
	for(int i=b;i>=a;--i)
	{
		dr[i]=dr[i+1]+el;
		el+=v[i];
	}
	for(int i=a;i+d<=b;++i)
		if (st[i]+dr[i+d]<r)
			r=st[i]+dr[i+d];
	return r;
}
	
int main ()
{
	read ();
	sol+=f(x,dx,X0,X1)+f(y,dy,Y0,Y1);
	ofstream fout ("tribute.out");
	fout<<sol;
	return 0;
}