Cod sursa(job #981729)

Utilizator roots4Irimia Alexandru Gabriel roots4 Data 7 august 2013 19:41:03
Problema Tribute Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.43 kb
#include<fstream>
#include<string.h>

#define c_max 50000
#define max_n 50010
#define inf 2000000000

using namespace std;

ifstream f("tribute.in");
ofstream g("tribute.out");

int n , dx , dy , tot;
int x[max_n] , y[max_n];

void read(){
	
	f>>n>>dx>>dy;
	
	for( int i = 1 ; i <= n ; i++ )
		f>>x[i]>>y[i];
	
}

int solve( int *v , int lenght ){
	
	int dist_st[c_max+2] , dist_dr[c_max+2];
	
	memset(dist_st , 0 , sizeof(dist_st));
	memset(dist_dr , 0 , sizeof(dist_st));
	
	int maxim = -1;
	
	for( int i = 1 ; i <= n ; i++ ){
		dist_st[v[i]]++; dist_dr[v[i]]++;
		if(v[i] > maxim)
			maxim = v[i];
	}
	
	int nr = 0;
	
	for( int i = 0 ; i <= maxim ; i++ ){
		
		if( i == 0 ){
			if(dist_st[i] != 0)
				nr += dist_st[i] , dist_st[i] = 0;
			continue;
		}
		
		if(dist_st[i] != 0)
			nr += dist_st[i] , dist_st[i] *= -1;
		dist_st[i] += dist_st[i-1] + nr;
		
	}
	
	nr = 0;
	
	for( int i = maxim ; i >= 0 ; i-- ){
		
		if( i == 10 )
			continue;
		
		if( dist_dr[i] != 0 )
			nr += dist_dr[i] , dist_dr[i] *= -1;
		dist_dr[i] += dist_dr[i+1] + nr;
		
	}
	
	int minim = inf , dist;
	
	for( int i = 0 ; i <= maxim ; i++ ){
		
		if( i + lenght > c_max )
			break;
		
		dist = dist_st[i] + dist_dr[i+lenght];
		
		if( dist < minim )	minim = dist;
		
	}
	
	return minim;
}

int main(){
	
	read();
	
	tot += solve(x , dx);
	tot += solve(y , dy);
	
	g<<tot<<"\n";
	
	return 0;
}