Cod sursa(job #2335889)

Utilizator anamariatoaderAna Toader anamariatoader Data 4 februarie 2019 16:51:17
Problema Tribute Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.04 kb
#include <fstream>

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

int n,i,dx,dy,x,y,mx,my;
long long d1,d2;
int fx[50005],fy[50005];
long long aux[50005],stx[50005],drx[50005],sty[50005],dry[50005];

int main()
{
    fin>>n>>dx>>dy;
    for(i=1;i<=n;i++){
        fin>>x>>y;
        mx=max(mx,x);
        my=max(my,y);
        fx[x]++;
        fy[y]++;
    }
    aux[0]=fx[0];
    for(i=1;i<=mx;i++){
        stx[i]=stx[i-1]+aux[i-1];
        aux[i]=aux[i-1]+fx[i];
    }
    for(i=mx;i>=0;i--){
        drx[i]=drx[i+1]+aux[i+1];
        aux[i]=aux[i+1]+fx[i];
    }
    aux[0]=fy[0];
    for(i=1;i<=my;i++){
        sty[i]=sty[i-1]+aux[i-1];
        aux[i]=aux[i-1]+fy[i];
    }
    aux[my+1]=0;
    for(i=my;i>=0;i--){
        dry[i]=dry[i+1]+aux[i+1];
        aux[i]=aux[i+1]+fy[i];
    }
    d1=(1<<60);
    for(i=0;i<=mx;i++)
        d1=min(d1,stx[i]+drx[i+dx]);
    d2=(1<<60);
    for(i=0;i<=my;i++)
        d2=min(d2,sty[i]+dry[i+dy]);
    fout<<d1+d2;
    return 0;
}