Cod sursa(job #1573064)

Utilizator andrei.arnautuAndi Arnautu andrei.arnautu Data 19 ianuarie 2016 12:41:53
Problema Tribute Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.24 kb
/**
  *  Worg
  */
#include <cstdio>
#include <algorithm>

using namespace std;
FILE *fin = freopen("tribute.in", "r", stdin);
FILE *fout = freopen("tribute.out", "w", stdout);

const int MAX_N = 50000;
const long long MAX_INF = 1000000000000000;

struct punct {

    int x;
    int y;
};

punct v[1 + MAX_N];
int n, dx, dy;

long long int sum[1 + MAX_N];
long long int sol1, sol2;

void readData() {

    scanf("%d%d%d", &n, &dx, &dy);
    for(int i = 1; i <= n; ++i)
        scanf("%d%d", &v[i].x, &v[i].y);
}

bool dupaX(const punct &p1, const punct &p2) {

    return p1.x < p2.x;
}

bool dupaY(const punct &p1, const punct &p2) {

    return p1.y < p2.y;
}

void baleiereDupaX() {

    sort(v + 1, v + n + 1, dupaX);
    for(int i = 1; i <= n; ++i)
        sum[i] = sum[i - 1] + v[i].x;

    int st, dr;
    int indSt = 1, indDr = 1;

    sol1 = MAX_INF;

    for(st = 0, dr = dx; dr <= MAX_N; st++, dr++) {

        while(indSt <= n && v[indSt].x <= st) {
            indSt++;
        }
        while(indDr <= n && v[indDr].x <= dr) {
            indDr++;
        }

        long long int a = 1LL * (indSt - 1) * st - sum[indSt - 1];
        long long int b;

        if(indDr > n) {
            b = 0;
        }
        else {
            b = sum[n] - sum[indDr - 1] - 1LL * (n - indDr + 1) * dr;
        }
        sol1 = min(sol1, a + b);
    }

}

void baleiereDupaY() {

    sort(v + 1, v + n + 1, dupaY);
    for(int i = 1; i <= n; ++i)
        sum[i] = sum[i - 1] + v[i].y;

    int st, dr;
    int indSt = 1, indDr = 1;

    sol2 = MAX_INF;

    for(st = 0, dr = dy; dr <= MAX_N; st++, dr++) {

        while(indSt <= n && v[indSt].y <= st) {
            indSt++;
        }
        while(indDr <= n && v[indDr].y <= dr) {
            indDr++;
        }

        long long int a = 1LL * (indSt - 1) * st - sum[indSt - 1];
        long long int b;

        if(indDr > n) {
            b = 0;
        }
        else {
            b = sum[n] - sum[indDr - 1] - 1LL * (n - indDr + 1) * dr;
        }

        sol2 = min(sol2, a + b);
    }
}

int main() {

    readData();

    baleiereDupaX();
    baleiereDupaY();
    printf("%lld", sol1 + sol2);

    return 0;
}