Cod sursa(job #1023839)

Utilizator CostanMiriamCostan Miriam CostanMiriam Data 7 noiembrie 2013 19:55:38
Problema Tribute Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.11 kb
#include <fstream>
using namespace std;
ifstream fin ("tribute.in");
ofstream fout("tribute.out");

long long xi[500005] , yi[500005], a,b,x,y,n,minim,minim1,i,s;
long long CS[500005] , CD[500005];


int main () {

    fin>>n>>x>>y;
    for (i=1;i<=n;i++) {
        fin>>a>>b;

        xi[a]++;
        yi[b]++;
    }
    minim=2000000000;
    minim1=2000000000;

    CS[0] = 0;

    for (i=1;i<=50000;i++) {
        CS[i] = CS[i-1] + xi[i-1];
        xi[i] += xi[i-1];
    }

    CD[50000] = 0;
    for (i=49999;i>=0;i--) {
        CD[i] = CD[i+1] + (xi[50000] - xi[i]);
    }

    for (i=0;i <= 50000-x;i++) {
        if (CS[i] + CD[i+x] < minim)
            minim = CS[i] + CD[i+x];
    }

    CS[0] = 0;

    for (i=1;i<=50000;i++) {
        CS[i] = CS[i-1] + yi[i-1];
        yi[i] += yi[i-1];
    }

    CD[50000] = 0;
    for (i=49999;i>=0;i--) {
        CD[i] = CD[i+1] + (yi[50000] - yi[i]);
    }

    for (i=0;i <= 50000 -y;i++) {
        if (CS[i] + CD[i+y] < minim1)
            minim1 = CS[i] + CD[i+y];
    }



    fout<<minim+minim1<<"\n";

    return 0;
}