Cod sursa(job #1573567)

Utilizator papinubPapa Victor papinub Data 19 ianuarie 2016 19:45:41
Problema Tribute Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.18 kb
#include <cstdio>
#include <algorithm>

using namespace std;

FILE *f = freopen("tribute.in", "r", stdin);
FILE *g = freopen("tribute.out", "w", stdout);

const int N_MAX= 5 * 1e5 + 1;
const long long MAX_INF = 1e15;

struct punct {

    int x;
    int y;
}v[N_MAX];

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;
}

int n, dx, dy;

long long sum[N_MAX], sol1, sol2;

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

void baleiereX()
{
    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 index_St = 1, index_Dr = 1;

    sol1 = MAX_INF;

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

        while(index_St <= n && v[index_St].x <= st) index_St++;
        while(index_Dr <= n && v[index_Dr].x <= dr) index_Dr++;

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

        if(index_Dr > n)
        {
            b = 0;
        }

        else

        {
            b = sum[n] - sum[index_Dr - 1] - 1LL * (n - index_Dr + 1) * dr;
        }

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

}

void baleiereY()
{
    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 index_St = 1, index_Dr = 1;

    sol2 = MAX_INF;

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

        while(index_St <= n && v[index_St].y <= st) index_St++;
        while(index_Dr <= n && v[index_Dr].y <= dr) index_Dr++;

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

        if(index_Dr > n)
        {
            b = 0;
        }

        else

        {
            b = sum[n] - sum[index_Dr - 1] - 1LL * (n - index_Dr + 1) * dr;
        }

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

int main()
{

    read();

    baleiereX();
    baleiereY();

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

    return 0;
}