Cod sursa(job #2335905)

Utilizator anamariatoaderAna Toader anamariatoader Data 4 februarie 2019 17:02:31
Problema Tribute Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.16 kb
#include <fstream>
#include <cstring>
#include <climits>
#include <algorithm>
#define N 50000

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<=N;i++){
        stx[i]=stx[i-1]+aux[i-1];
        aux[i]=aux[i-1]+fx[i];
    }
    memset(aux,0,sizeof(aux));
    for(i=N;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<=N;i++){
        sty[i]=sty[i-1]+aux[i-1];
        aux[i]=aux[i-1]+fy[i];
    }
    memset(aux,0,sizeof(aux));
    for(i=N;i>=0;i--){
        dry[i]=dry[i+1]+aux[i+1];
        aux[i]=aux[i+1]+fy[i];
    }
    d1=LLONG_MAX;
    for(i=0;i<=N-dx;i++)
        d1=min(d1,stx[i]+drx[i+dx]);
    d2=LLONG_MAX;
    for(i=0;i<=N-dy;i++)
        d2=min(d2,sty[i]+dry[i+dy]);
    fout<<d1+d2;
    return 0;
}