Cod sursa(job #2192545)

Utilizator Al3ks1002Alex Cociorva Al3ks1002 Data 6 aprilie 2018 15:11:41
Problema Tribute Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.24 kb
#include <stdio.h>
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define ld long double
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pdd pair<ld, ld>
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second

const int kMaxN = 50000;
const ll kInf = 1LL << 62;

ll Solve(vector<int>& cnt, int d) {
  vector<ll> sum(kMaxN + 1);
  for (int i = 1; i <= kMaxN; i++) {
    sum[i] += 1LL * cnt[i] * i;
    sum[i] += sum[i - 1];
    cnt[i] += cnt[i - 1];
  }

  ll ans = kInf;
  for (int i = d; i <= kMaxN; i++) {
    int a = i - d;
    int b = i;
    ll curr = 0;

    if (a > 0) {
      curr += 1LL * a * cnt[a - 1] - sum[a - 1];
    }
    if (b < kMaxN) {
      curr += (sum[kMaxN] - sum[b]) - 1LL * b * (cnt[kMaxN] - cnt[b]);
    }

    ans = min(ans, curr);
  }

  return ans;
}

int main() {
  cin.sync_with_stdio(false);

  ifstream cin("tribute.in");
  /* ofstream cout("tribute.out"); */

  int n, dx, dy;
  cin >> n >> dx >> dy;

  vector<int> cnt_x(kMaxN + 1);
  vector<int> cnt_y(kMaxN + 1);
  for (int i = 1; i <= n; i++) {
    int x, y;
    cin >> x >> y;
    cnt_x[x]++;
    cnt_y[y]++;
  }

  cout << Solve(cnt_x, dx) + Solve(cnt_y, dy) << '\n';

  return 0;
}