Cod sursa(job #1758280)

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

int x[MaxN],y[MaxN],N,Dx,Dy;
int GetMin(int v[],int dist)
{
	int 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("%d",GetMin(x,Dx)+GetMin(y,Dy));
	return 0;
}