Cod sursa(job #1365737)

Utilizator Theodor1000Cristea Theodor Stefan Theodor1000 Data 28 februarie 2015 14:46:33
Problema Tribute Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.03 kb
#include <cstdio>
#include <algorithm>

using namespace std;

int n, a[50010], b[50010], v[50010], st[50010], dr[50010], drr[50010];

inline int calc (int a[50010], int l)
{
    for (int i = 1; i <= n; ++i)
        ++v[a[i]];

    for (int i = 1; i <= 50000; ++i)
        st[i] = st[i - 1] + v[i - 1];

    for (int i = 50000; i >= 0; --i)
        dr[i] = dr[i + 1] + v[i + 1];

    for (int i = 50000; i >= 0; --i)
        drr[i] = drr[i + 1] + dr[i];

    int x = 0, mi = 2000000000;
    for (int i = 0; i <= 50000 - l; ++i)
    {
        x += st[i];
        int y = x + drr[i + l];

        mi = min (mi, y);
    }

    for (int i = 1; i <= n; ++i)
        v[a[i]] = 0;

    return mi;
}

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

    int dx, dy;
    scanf ("%d %d %d", &n, &dx, &dy);

    for (int i = 1; i <= n; ++i)
        scanf ("%d %d", &a[i], &b[i]);

    int rez = calc (a, dx) + calc (b, dy);
    printf ("%d\n", rez);

    return 0;
}