Cod sursa(job #1872610)

Utilizator doc2177Dorian Croitoru doc2177 Data 8 februarie 2017 13:51:25
Problema Tribute Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.8 kb
#include <bits/stdc++.h>

using namespace std;

int ans(const vector<int> & v, int d) {
	const int N=int(v.size()), A=v[0], B=v.back(); 
	int current=0, ix=0, jx=0;
	
	while (v[ix]<= A) ix++; 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+1+jx - N;
		while (i==v[ix+1]) 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,a,b,DX,DY; 
	cin >> N >> DX >> DY;
	vector<int> horiz(N), vert(N);

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

	sort(horiz.begin(), horiz.end());
	sort(vert.begin(), vert.end());

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