Cod sursa(job #1134194)

Utilizator negreadumitruNegrea Dumitru negreadumitru Data 6 martie 2014 10:20:43
Problema Tribute Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.42 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;
}