Cod sursa(job #554296)

Utilizator bora_marianBora marian bora_marian Data 14 martie 2011 18:59:07
Problema Tribute Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.12 kb
#include<fstream>
#include<algorithm>
#define ll long long
#define DIM 50005
using namespace std;
long long st[DIM],dr[DIM];
ll minx=50001,maxx,caractx[DIM],caracty[DIM],miny=50002,maxy,n,X,Y,x[DIM],y[DIM];	
ll solve(ll v[],ll caract[],ll mini,ll maxi,ll d);
int main()
{
	ifstream fin("tribute.in");
	ofstream fout("tribute.out");
	fin>>n>>X>>Y;
	int i;
	for(i=1;i<=n;i++)
	{
	   fin>>x[i]>>y[i];
	   caractx[x[i]]++;
	   caracty[y[i]]++;
	   if(x[i]<minx)
	     minx=x[i];
	   if(x[i]>maxx)
	     maxx=x[i];
	   if(y[i]<miny)
	      miny=y[i];
	   if(y[i]>maxy)
	     maxy=y[i];       
	}
	fout<<solve(x,caractx,minx,maxx,X)+solve(y,caracty,miny,maxy,Y);   
}
ll solve(ll v[],ll caract[],ll mini,ll maxi,ll d)
{	
	ll minn=3243543,i;
	ll el=0;
	for(i=1;i<=maxi+1;i++)
	   st[i]=dr[i]=0;   
	for(i=mini;i<=maxi;i++)
	    if(i>=1)
	       st[i]=st[i-1]+el,
	       el+=caract[i];
	     else
	       el+=caract[i];  
	el=0;   
	for(i=maxi;i>=mini;i--)   
		dr[i]=dr[i+1]+el,
		el+=caract[i];
	if(mini+d<=maxi)
	{
	  for(i=mini;i+d<=maxi;i++)
	     if(st[i]+dr[i+d]<minn)
	       minn=st[i]+dr[i+d];
	 }
	 else
	   minn=0; 
	return minn;
}