Cod sursa(job #519936)

Utilizator AndreyPAndrei Poenaru AndreyP Data 6 ianuarie 2011 22:30:58
Problema Tribute Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <cstdio>
#include <algorithm>
using namespace std;
#define N 50010
#define ll long long

int n,dx,dy;
int x[N],y[N];
int s1[N],s2[N];

inline void citire() {
	scanf("%d%d%d",&n,&dx,&dy);
	for(int i=1; i<=n; ++i) {
		scanf("%d%d",&x[i],&y[i]);
	}
}

inline ll rezolva(int v[N],int dv) {
	int i,j;
	sort(v+1,v+n+1);
	ll ret = 1e13,aux;
	for(i=1; i<=n; ++i)
		s1[i] = s1[i-1]+(ll)v[i];
	for(i=n; i>0; --i)
		s2[i] = s2[i+1]+(ll)v[i];
	if(v[n]-v[1]<=dv)
		return 0LL;

	i = 0;
	j = 1;

	for(int t=v[1],lim=v[n]-dv+1; t<lim; ++t) {
		aux = 0;
		for(; v[i]<t; ++i)
			;
		if(i>1)
			aux = (ll)t*(ll)(i-1)-s1[i-1];
		for(; v[j]<=t+dv && j<=n; ++j)
			;
		if(j>n)
			--j;
		else {
			if(v[j]>t+dv)
				--j;
		}
		aux += s2[j+1]-(ll)(t+dv)*(ll)(n-j);
		if(ret>aux)
			ret = aux;
	}

	return ret;
}

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

	citire();
	printf("%lld\n",rezolva(x,dx)+rezolva(y,dy));

	return 0;
}