Cod sursa(job #2727973)

Utilizator biancalautaruBianca Lautaru biancalautaru Data 22 martie 2021 17:50:38
Problema Tribute Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.86 kb
#include <fstream>
#include <climits>
#define DIM 50001
using namespace std;
ifstream fin("tribute.in");
ofstream fout("tribute.out");
int n,dx,dy,i,mini,x[DIM],y[DIM],f[DIM],st[DIM],dr[DIM],sp1[DIM],sp2[DIM];

int rez(int v[],int d) {
    for (i=0;i<=50000;i++)
        f[i]=0;
    for (i=1;i<=n;i++)
        f[v[i]]++;
    st[0]=0;
    sp1[0]=f[0];
    for (i=1;i<=50000;i++) {
        st[i]=st[i-1]+sp1[i-1];
        sp1[i]=sp1[i-1]+f[i];
    }
    dr[50000]=0;
    sp2[50000]=f[50000];
    for (i=49999;i>=0;i--) {
        dr[i]=dr[i+1]+sp2[i+1];
        sp2[i]=sp2[i+1]+f[i];
    }
    mini=INT_MAX;
    for (i=1;i+d<=50000;i++)
        if (st[i]+dr[i+d]<mini)
            mini=st[i]+dr[i+d];
    return mini;
}

int main() {
    fin>>n>>dx>>dy;
    for (i=1;i<=n;i++)
        fin>>x[i]>>y[i];
    fout<<rez(x,dx)+rez(y,dy);
    return 0;
}