Cod sursa(job #1491049)

Utilizator vladrochianVlad Rochian vladrochian Data 24 septembrie 2015 18:27:53
Problema Tribute Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.7 kb
#include <fstream>
using namespace std;

const int kMaxC = 50001;

ifstream fin("tribute.in");
ofstream fout("tribute.out");

int N, DX, DY;
int cntx[kMaxC], cnty[kMaxC];

int64_t Solve(int d, int *cnt) {
  int l = 0, r = 0;
  int64_t s = 0, ans = 6e9;
  for (int i = kMaxC - 1; i >= d; --i) {
    r += cnt[i];
    s += r;
  }
  for (int i = 0; i < kMaxC - d; ++i) {
    s -= r;
    r -= cnt[i + d];
    ans = min(ans, s);
    l += cnt[i];
    s += l;
  }
  return ans;
}

int main() {
  fin >> N >> DX >> DY;
  for (int i = 0; i < N; ++i) {
    int x, y;
    fin >> x >> y;
    ++cntx[x];
    ++cnty[y];
  }
  fout << Solve(DX, cntx) + Solve(DY, cnty) << "\n";
  return 0;
}