Cod sursa(job #2670586)

Utilizator lucametehauDart Monkey lucametehau Data 10 noiembrie 2020 11:49:48
Problema Tribute Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.78 kb
#include <bits/stdc++.h>
#define x first
#define y second
#define ll long long

using namespace std;

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

int n, dx, dy;

int x[50005], y[50005];
ll s[50005];

ll solve(int v[], int d) {
  ll ans = (ll)1e18;
  int l = 1, r = 1;
  sort(v + 1, v + n + 1);
  for(int i = 1; i <= n; i++)
    s[i] = s[i - 1] + v[i];
  for(int x = 1; x <= 50000; x++) {
    while(v[l] <= x && l <= r)
      l++;
    while(v[r] <= x + dx && r <= n)
      r++;
    ans = min(ans, 1LL * x * (l - 1) - s[l - 1] + (s[n] - s[r - 1]) - 1LL * (x + dx) * (n - r + 1));
  }
  return ans;
}

int main() {
  in >> n >> dx >> dy;
  for(int i = 1; i <= n; i++)
    in >> x[i] >> y[i];
  out << solve(x, dx) + solve(y, dy);
  return 0;
}