Cod sursa(job #1758279)

Utilizator GabiTulbaGabi Tulba-Lecu GabiTulba Data 16 septembrie 2016 21:54:52
Problema Tribute Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include <cstdio>
#include <algorithm>
#define INF 500000000000
#define MaxN 500001
using namespace std;

long long x[MaxN],y[MaxN],N,Dx,Dy;
long long GetMin(long long v[],long long dist)
{
	long long i=0,j=dist,posi=1,posj=1,Min=INF;
	while(v[posi]-v[posi-1]<=i)
	{
		if(posi==N)break;
		posi++;
	}
	posi--;
	while(v[posj]-v[posj-1]<=j)
	{
		if(posj==N)break;
		posj++;
	}
	posj--;
	while(posj<=N)
	{
		Min=min(Min,abs(i*posi-v[posi])+abs(j*(N-posj)-v[N]+v[posj]));
		if(posj==N)break;
		i++,j++;
		while(v[posi]-v[posi-1]<=i)
		{
			if(posi>N)break;
			posi++;
		}
		posi--;
		while(v[posj]-v[posj-1]<=j)
		{
			if(posj>N)break;
			posj++;
		}
		posj--;
	}
	return Min;
}
int main()
{
    freopen("tribute.in","r",stdin);
    freopen("tribute.out","w",stdout);
	
	scanf("%d%d%d",&N,&Dx,&Dy);
	for(int i=1;i<=N;i++)
		scanf("%d%d",&x[i],&y[i]);
	sort(x+1,x+1+N);
	sort(y+1,y+1+N);
	for(int i=1;i<=N;i++)
		x[i]+=x[i-1],y[i]+=y[i-1];
	printf("%lld",GetMin(x,Dx)+GetMin(y,Dy));
	return 0;
}