Cod sursa(job #383010)

Utilizator freak93Adrian Budau freak93 Data 15 ianuarie 2010 12:12:11
Problema Tribute Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.23 kb
#include<fstream>
#include<algorithm>

using namespace std;

const char iname[]="tribute.in";
const char oname[]="tribute.out";
const int maxn=50007;
const int INF=(1<<31)-1;

ifstream f(iname);
ofstream g(oname);

int i,j,n,X[maxn],Y[maxn],cost,mint,dx,dy,start,end,rez;

int main()
{
    f>>n>>dx>>dy;
    for(i=1;i<=n;++i)
        f>>X[i]>>Y[i];
    sort(X+1,X+n+1);
    end=n+1;
    start=0;
    mint=INF;
    for(i=1;i<=n;++i)
        if(X[i]>dx)
            cost+=X[i]-dx,end=min(end,i);
    for(i=1;i<maxn;++i)
    {
        while(start<n&&X[start+1]<i)
            ++start;
        cost+=start-n+end-1;
        while(end<=n&&X[end]<=i+dx)
            ++end;
        if(cost<mint)
            mint=cost;
    }
    rez+=mint;

    sort(Y+1,Y+n+1);
    end=n+1;
    start=0;
    mint=INF;
    cost=0;
    for(i=1;i<=n;++i)
        if(Y[i]>dy)
            cost+=Y[i]-dy,end=min(end,i);
    for(i=1;i<maxn;++i)
    {
        while(start<n&&Y[start+1]<i)
            ++start;
        cost+=start-n+end-1;
        while(end<=n&&Y[end]<=i+dy)
            ++end;
        if(cost<mint)
            mint=cost;
    }
    rez+=mint;

    g<<rez<<"\n";

    f.close();
    g.close();

    return 0;
}