Cod sursa(job #672324)

Utilizator alutzuAlexandru Stoica alutzu Data 1 februarie 2012 21:03:24
Problema Tribute Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 kb
#include <cstdio>

long long fx[2*50005], fy[2*50005], X[2*50005], Y[50005] ;

struct PUNCT {
	long long x , y ;
};

PUNCT punct[50005];

int main ( )
{
	
	freopen ( "tribute.in", "r", stdin ) ;
	freopen ( "tribute.out", "w", stdout ) ;
	
	long long N , DX , DY , S = 0 ;
	long long min = (long long)1<<60 ;
	long long minn = (long long)1<<60 ;
	long long i ;
	
	scanf ( "%lld%lld%lld", & N , & DX , & DY ) ;
	
	for ( i = 1 ; i <= N ; ++ i )
	{
		scanf ( "%lld%lld" , &punct[i].x ,&punct[i].y ) ;
		++ fx [ punct[i].x ] ;
		++ fy [ punct[i].y ] ;
	}

	X[0] = fx[0] ;
	Y[0] = fy[0] ;
	
	for ( i = 1 ; i <= 50000 ; ++ i ) 
	{
		X [i] = X[i-1] + fx[i] ;
		Y [i] = Y[i-1] + fy[i] ;
	}
	
	for ( i = 0+DX ; i <= 50000 ; ++ i )
	{
		if ( fx[i] )
		{
			S += fx[i]*(i-DX) ;
		}
	}
	min = S;
	for ( i = 1 ; i <= 50000-DX ; ++ i )
	{
		S += X[i-1] ;
		S -= ( N - X[i+DX-1] ) ;
		if ( S < min )
		{
			min = S ;
		}
	}
	S = 0 ;
	for ( i = 0+DY ; i <= 50000 ; ++ i )
	{
		if ( fy[i] )
		{
			S += fy[i]*(i-DY) ;
		}
	}
	minn = S;
	for ( i = 1 ; i <= 50000-DY ; ++ i )
	{
		S += Y[i-1] ;
		S -= ( N - Y[i+DY-1] ) ;
		if ( S < minn )
		{
			minn = S ;
		}
	}
	
	
	printf ( "%lld" , min + minn ) ;
	
	
	return 0 ;
}