Cod sursa(job #1607510)

Utilizator cristina_borzaCristina Borza cristina_borza Data 21 februarie 2016 12:16:17
Problema Tribute Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.2 kb
#include <algorithm>
#include <fstream>
#include <cstdio>

#define INF 1000000000
#define NMAX 50005

using namespace std;

int n , dx , dy , soly = INF , solx = INF , mx , my , inc , sf , nr;
int vx[NMAX] , vy[NMAX] , sumst[NMAX] , sumdr[NMAX];

void read(int &x) {
    bool sign = 1;
    char ch;

    while(!isdigit(ch = getchar())) {
        if(ch == '-')
            sign = -1;
        else
            sign = 1;
    }

    do {
        x = x * 10 + ch - '0';
    }while(isdigit(ch = getchar()));

    x *= sign;
}

int caut_bin(int val , bool x , int v[]);

int main() {
    freopen("tribute.in" , "r" , stdin);
    freopen("tribute.out" , "w" , stdout);

    read(n) , read(dx) , read(dy);
    for(int i = 1 ; i <= n ; ++i) {
        read(vx[i]) , read(vy[i]);
        mx = max(mx , vx[i]);
        my = max(my , vy[i]);
    }

    sort(vx + 1 , vx + n + 1);

    for(int i = 1 ; i <= n ; ++i) {
        sumst[i] = sumst[i - 1] + mx - vx[i];
    }

    for(int i = n ; i >= 1 ; --i) {
        sumdr[i] = sumdr[i + 1] + vx[i];
    }

    for(int i = 0 ; i <= mx ; ++i) {
        inc = i;
        sf = i + dx;

        int p1 = caut_bin(sf , 1 , vx);
        int p2 = caut_bin(inc , 0 , vx);

        nr = sumdr[p1] - sf * (n - p1 + 1) + sumst[p2] - (mx - inc) * p2;
        solx = min(solx , nr);
    }

    sort(vy + 1 , vy + n + 1);

    sumst[0] = 0;
    for(int i = 1 ; i <= n ; ++i) {
        sumst[i] = sumst[i - 1] + my - vy[i];
    }

    sumdr[n + 1] = 0;
    for(int i = n ; i >= 1 ; --i) {
        sumdr[i] = sumdr[i + 1] + vy[i];
    }

    for(int i = 0 ; i <= my ; ++i) {
        inc = i;
        sf = i + dy;

        int p1 = caut_bin(sf , 1 , vy);
        int p2 = caut_bin(inc , 0 , vy);

        nr = sumdr[p1] - sf * (n - p1 + 1) + sumst[p2] - (my - inc) * p2;
        soly = min(soly , nr);
    }

    printf("%d" , solx + soly);
    return 0;
}


int caut_bin(int val , bool x , int v[]) {
    int i , p = 0;
    for(i = 1 ; i <= n ; i <<= 1);
    while(i) {
        if(i + p <= n && v[i + p] <= val) {
            p += i;
        }

        i >>= 1;
    }

    if(x == 1) {
        ++p;
    }

    return p;
}