Cod sursa(job #1872677)

Utilizator doc2177Dorian Croitoru doc2177 Data 8 februarie 2017 14:42:06
Problema Tribute Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.76 kb
#include <bits/stdc++.h>
#define NMAX 50002
using namespace std;

int ans(const int & N, const int & d, int * v) {
	const int A=v[0], B=v[N-1]; 
	int current=0, ix=0, jx=0;
	
	while (v[ix]<= A) ix++;  	
	while (v[jx]<= A+d) jx++ ; 
	
	for (int i=jx; i<N; i++) current+= (v[i]-A-d);
	
	int mn = current;
	for (int i=A+1; i<=B-d; i++) {
		current+= ix+jx - N;
		while (i==v[ix]) ix++; 
		while (i+d==v[jx]) jx++;
		mn = min(mn, current);
	}
	return mn;
}

int main() {
	freopen("tribute.in","r", stdin);
	freopen("tribute.out","w", stdout);

	int N,DX,DY, horiz[NMAX], vert[NMAX]; 
	cin >> N >> DX >> DY;

	for (int i=0; i!=N; ++i) cin >> horiz[i] >> vert[i]; 

	sort(horiz, horiz+N);
	sort(vert, vert+N);

	cout << ans(N, DX, horiz) + ans(N, DY, vert) << endl ;
	return 0;
}