Cod sursa(job #164898)

Utilizator andrei.12Andrei Parvu andrei.12 Data 24 martie 2008 22:17:42
Problema Tribute Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.38 kb
#include<stdio.h>
#include<algorithm>

using namespace std;

#define lg 50005

int n, dx, dy, i, x, y, v1[lg], v2[lg], d1, d2;

int bs1(int v[], int val){
	int li = 1, ls = n, x, gs = 0;

	while (li <= ls){
		x = (li + ls) / 2;

		if (v[x] <= val){
			gs = x;
			li = x+1;
		}
		else
			ls = x-1;
	}

	return gs;
}
int bs2(int v[], int val){
	int li = 1, ls = n, x, gs = 0;

	while (li <= ls){
		x = (li + ls) / 2;
		
		if (v[x] >= val){
			gs = x;

			ls = x-1;
		}
		else
			li = x+1;
	}

	return gs;
}
int find(int v[], int val){
	int i, x1, x2, dr[lg] = {0}, st[lg] = {0}, mn = 0x3f3f3f3f;

	for (i = 2; i <= n; i ++)
		st[i] = st[i-1] + (i-1) * (v[i]-v[i-1]);
	for (i = n-1; i; i --)
		dr[i] = dr[i+1] + (n-i) * (v[i+1] - v[i]);

	for (i = 1; i <= 50000; i ++){
		x1 = bs1(v, i);
		x2 = bs2(v, i+val);

		if (st[x1] + x1*(i-v[x1]) + dr[x2] + (n-x2+1)*(v[x2] - i - val) < mn)
			mn = st[x1] + x1*(i-v[x1]) + dr[x2] + (n-x2+1)*(v[x2] - i - val);
		
//		printf("%d %d %d\n", x1, x2, mn);
	}

	return mn;
}
int main()
{
	freopen("tribute.in", "rt", stdin);
	freopen("tribute.out", "wt", stdout);

	scanf("%d%d%d", &n, &dx, &dy);
	memset(v1, 0x3f, lg*sizeof(int));
	memset(v2, 0x3f, lg*sizeof(int));
	for (i = 1; i <= n; i ++){
		scanf("%d%d", &x, &y);

		v1[i] = x;
		v2[i] = y;
	}
	
	sort(v1+1, v1+n+1);
	sort(v2+1, v2+n+1);

	d1 = find(v1, dx);
	d2 = find(v2, dy);

	printf("%d\n", d1 + d2);

	return 0;
}