Cod sursa(job #2298149)

Utilizator radugheoRadu Mihai Gheorghe radugheo Data 7 decembrie 2018 16:55:19
Problema Tribute Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.22 kb
#include <fstream>
#include <climits>
#define DIM 50005
#define DIM2 50000

using namespace std;

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

struct punct {
    int x;
    int y;
};

int n, a, b, i, sum, mi;
int f[DIM], s[DIM], d[DIM], ps[DIM], pd[DIM];

punct p[DIM];

inline void swp (){
    int i;
    for (i=1; i<=n; i++){
        swap (p[i].x, p[i].y);
    }
}

inline void initializare (){
    int i;
    for (i=0; i<=DIM2; i++){
        f[i] = 0;
    }
}

inline int solve (int x){
    int i, st, dr;
    initializare();
    for (i=1; i<=n; i++){
        f[p[i].x]++;
    }
    s[0] = 0;
    ps[0] = f[0];
    for (i=1; i<=DIM2; i++){
        s[i] = s[i-1] + ps[i-1];
        ps[i] = ps[i-1] + f[i];
    }
    d[DIM2] = 0;
    pd[DIM2] = f[DIM2];
    for (i=DIM2-1; i>=0; i--){
        d[i] = d[i+1] + pd[i+1];
        pd[i] = pd[i+1] + f[i];
    }
    mi = INT_MAX;
    for (st=0; st+x<=DIM2; st++){
        mi = min (mi, s[st] + d[st+x]);
    }
    return mi;
}

int main(){
    fin >> n >> a >> b;
    for (i=1; i<=n; i++){
        fin >> p[i].x >> p[i].y;
    }
    sum += solve (a);
    swp ();
    sum += solve (b);
    fout << sum;
    return 0;
}