Pagini recente » Cod sursa (job #1515499) | Cod sursa (job #1005878) | Cod sursa (job #3248427) | Cod sursa (job #1419517) | Cod sursa (job #1134194)
#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;
}