Cod sursa(job #1125497)

Utilizator raulstoinStoin Raul raulstoin Data 26 februarie 2014 17:59:09
Problema Tribute Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.22 kb
#include<fstream>
#include<algorithm>
#include<vector>

#define NMAX 50005

using namespace std;

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

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

int f(int start,int stop,int D,int *S,vector<int> &V)
{
	int minim=(1<<30);
	for(int i=start;i<=stop;i++)
	{
		int d=0,ind;
		ind=(int)(upper_bound(V.begin(),V.end(),i-1)-V.begin()); //sub
		if(ind>0 && ind<n)
			d+=(ind)*i-S[V[ind-1]];
		ind=(int)(upper_bound(V.begin(),V.end(),i+D)-V.begin()); //deasupra
		if(ind>0 && ind<n)
			d+=S[stop]-(n-ind)*(i+D)-S[V[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;
		sx[x]+=x;
		sy[y]+=y;
		if(!x)
			X.push_back(0);
		if(!y)
			Y.push_back(0);
		xstart=min(xstart,x);
		ystart=min(ystart,y);
		xstop=max(xstop,x);
		ystop=max(ystop,y);
	}
	for(int i=1;i<NMAX;i++)
	{
		for(int j=sx[i];j;j-=i)
			X.push_back(i);
		for(int j=sy[i];j;j-=i)
			Y.push_back(i);
	}
	for(int i=1;i<=xstop;i++)
		sx[i]+=sx[i-1];
	for(int i=1;i<=ystop;i++)
		sy[i]+=sy[i-1];
	fout<<f(xstart,xstop,dx,sx,X)+f(ystart,ystop,dy,sy,Y);
	return 0;
}