Cod sursa(job #1125331)

Utilizator raulstoinStoin Raul raulstoin Data 26 februarie 2014 16:58:24
Problema Tribute Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.12 kb
#include<fstream>
#include<algorithm>
#include<vector>

#define NMAX 50000

using namespace std;

ifstream fin("tribute.in");
ofstream fout("tribute.out");

int n,dx,dy,sx[NMAX+5],sy[NMAX+5],xstart=(1<<30),ystart=(1<<30),xstop,ystop;
vector<int> X,Y;
vector<int>::iterator it,it2;

int f(int start,int stop,int D,int *S,vector<int> &V)
{
	int minim=(1<<30);
	for(int i=start;i<=stop-D;i++)
	{
		int d=0,ind;
		ind=(int)(upper_bound(V.begin(),V.end(),i-1)-V.begin()); //sub
		if(ind>0)
			d+=(ind)*i-S[ind-1];
		ind=(int)(upper_bound(V.begin(),V.end(),i+D)-V.begin()); //deasupra
		if(ind<n)
			d+=S[NMAX]-(n-ind)*(i+D)-S[ind-1];
		minim=min(minim,d);
	}
	return minim;
}

int main()
{
	fin>>n>>dx>>dy;
	for(int i=1,x,y;i<=n;i++)
	{
		fin>>x>>y;
		X.push_back(x);
		Y.push_back(y);
		sx[x]+=x;
		sy[y]+=y;
		xstart=min(xstart,x);
		ystart=min(ystart,y);
		xstop=max(xstop,x);
		ystop=max(ystop,y);
	}
	sort(X.begin(),X.end());
	sort(Y.begin(),Y.end());
	for(int i=1;i<=NMAX;i++)
	{
		sx[i]+=sx[i-1];
		sy[i]+=sy[i-1];
	}
	fout<<f(xstart,xstop,dx,sx,X)+f(ystart,ystop,dy,sy,Y);
	return 0;
}