Cod sursa(job #2261813)

Utilizator mouse_wirelessMouse Wireless mouse_wireless Data 16 octombrie 2018 18:40:54
Problema Tribute Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.22 kb
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define mp make_pair
#define CHECK(x) if(!(x)) return false;
#define CHECKRET(x, y) if(!(x)) return (y);
#define SKIP(x) if((x)) continue;
typedef pair<int, int> pii;

#ifdef INFOARENA
#define ProblemName "tribute"
#endif

#define MCONCAT(A, B) A B
#ifdef ProblemName
#define InFile MCONCAT(ProblemName, ".in")
#define OuFile MCONCAT(ProblemName, ".out")
#else
#define InFile "fis.in"
#define OuFile "fis.out"
#endif

const int MAXN = 50010;
int xf[MAXN], yf[MAXN];

LL process(int *f, int d) {
  int ptsAfter = 0, ptsBefore = 0;
  int s = 0, e = d;
  LL cur = 0;
  for (int i = e + 1; i < MAXN; ++i) {
    ptsAfter += f[i];
    cur += 1LL * f[i] * (i - e);
  }
  LL best = cur;
  for (; e < MAXN;
    ptsBefore += f[s], ++s,
    cur += ptsBefore - ptsAfter,
    best = min(best, cur),
    ++e, ptsAfter -= f[e]);
  return best;
}

int main() {
  assert(freopen(InFile, "r", stdin));
  assert(freopen(OuFile, "w", stdout));
  int N, dx, dy;
  scanf("%d%d%d", &N, &dx, &dy);
  while(N--) {
    int x, y;
    scanf("%d%d", &x, &y);
    ++xf[x], ++yf[y];
  }
  printf("%lld\n", process(xf, dx) + process(yf, dy));
  return 0;
}