Cod sursa(job #1897575)

Utilizator antanaAntonia Boca antana Data 1 martie 2017 15:56:22
Problema Tribute Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.33 kb
#include <cstdio>
#include <cstring>
#include <algorithm>

#define MAXN 50001

using namespace std;

struct point{
    int x, y;
}v[MAXN];

int DX, DY, n, maxC, d[MAXN];
long long answer, left[MAXN], right[MAXN];

long long compute(int D)
{
    int i, points = 0;
    long long minSum;

    memset(d, 0, sizeof d);
    memset(left, 0, sizeof left);
    memset(right, 0, sizeof right);

    for(i=1; i<=n; ++i)
        d[v[i].x]++;

    left[0] = 0;
    points = d[0];
    for(i=1; i<=maxC; ++i) {
        left[i] = left[i-1] + points;
        points += d[i]; }

    points = d[maxC];
    right[maxC] = 0;
    for(i=maxC-1; i>=0; --i) {
        right[i] = right[i+1] + points;
        points += d[i]; }

    minSum = left[0] + right[D];
    for(i=1; i<=maxC-D; ++i)
        minSum = min(minSum, left[i] + right[D+i]);

    return minSum;
}

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

    int i;

    scanf("%d%d%d", &n, &DX, &DY);

    for(i=1; i<=n; ++i) {
        scanf("%d%d", &v[i].x, &v[i].y);
        maxC = max(maxC, v[i].x); }

    answer += compute(DX);

    maxC = 0;
    for(i=1; i<=n; ++i) {
        swap(v[i].x, v[i].y);
        maxC = max(maxC, v[i].x); }

    answer += compute(DY);

    printf("%lld", answer);

    return 0;
}