Cod sursa(job #519924)

Utilizator AndreyPAndrei Poenaru AndreyP Data 6 ianuarie 2011 21:51:47
Problema Tribute Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.89 kb
#include <cstdio>
#include <algorithm>
using namespace std;
#define N 50010
#define ll long long

int n,dx,dy;
int x[N],y[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) {
	sort(v+1,v+n+1);
	ll s1=0,s2=0;
	ll ret = 1e13,aux;
	for(int i=1; i<=n; ++i)
		s2 += v[i];
	if(v[n]-v[1]<=dv)
		return 0LL;

	int i=0,j=1;

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

		aux = ((ll)t*(ll)i)-s1+s2-((ll)n-(ll)j)*(ll)(t+dv);
		if(aux<ret)
			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;
}