Cod sursa(job #428079)

Utilizator klamathixMihai Calancea klamathix Data 28 martie 2010 19:58:46
Problema Tribute Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.22 kb
#include<fstream>
#include<algorithm>
#include<vector>
#define pb push_back
#define ll long long
using namespace std;
const int MAXCOORD = 50001;
ifstream in("tribute.in");
ofstream out("tribute.out");
ll int i , j , n , dx , dy , mins1 = 10000000000LL , mins2 = 10000000000LL;
int it1,it2,a,b;
vector <int> x;
vector <int> y;
int Bx[MAXCOORD] , By[MAXCOORD] , cnt_x[2 * MAXCOORD] , cnt_y[2 * MAXCOORD];
int main()
{
	in >> n >> dx >> dy;
	for( i = 1 ; i <= n ; ++i ) {
		in >> a >> b;
		x.pb(a) , y.pb(b);
		cnt_x[a]++ , cnt_y[b]++;
	}
	
	for( i = 1 ; i <= MAXCOORD ; ++i )
		cnt_x[i] += cnt_x[i - 1] ,
		cnt_y[i] += cnt_y[i - 1];
	
	for( i = 0 ; i < x.size() ; ++i )
		if ( x[i] > dx ) Bx[0] += x[i] - dx;
	if ( Bx[0] < mins1 ) mins1 = Bx[0];
		
	for ( i = 1 ; i <= MAXCOORD ; ++i ) {
		Bx[i] = Bx[i - 1] + cnt_x[i - 1] - ( n - cnt_x[i + dx - 1] );
		if ( Bx[i] < mins1 ) mins1 = Bx[i];
	}
	
	for( i = 0 ; i < y.size() ; ++i )
		if ( y[i] > dy ) By[0] += y[i] - dy;
	
	if ( By[0] < mins2 ) mins2 = By[0];
	for ( i = 1 ; i <= MAXCOORD ; ++i ) {
		By[i] = By[i - 1] + cnt_y[i - 1] - ( n - cnt_y[i + dy - 1] );
		if ( By[i] < mins2 ) mins2 = By[i];
	}
	out << 1LL*( mins1 + mins2) << "\n";
	
return 0;
}