Cod sursa(job #2900609)

Utilizator iancupoppPopp Iancu Alexandru iancupopp Data 11 mai 2022 15:31:25
Problema Tribute Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.1 kb
#include <fstream>
#include <vector>
#include <cstring>

using namespace std;

const int N = 5e4 + 5;

int cate[N];
long long sum[N];

long long calc(vector<int>& v, const int d) {
  for (auto i: v)
    ++cate[i], sum[i] += i;
  for (int i = 1; i < N; ++i) {
    cate[i] += cate[i - 1];
    sum[i] += sum[i - 1];
  }
  long long ans = (1LL << 60);
  for (int i = 0; i < N; ++i) {
    long long add_st = 0, add_dr = 0;
    if (i > 0)
      add_st = 1LL * cate[i - 1] * i - sum[i - 1];
    if (i + d < N)
      add_dr = (sum[N - 1] - sum[i + d - 1]) - 1LL * (cate[N - 1] - cate[i + d - 1]) * (i + d);
    ans = min(ans, add_st + add_dr);
  }
  return ans;
}

int main() {
  ifstream cin("tribute.in");
  ofstream cout("tribute.out");
  int n, dx, dy;
  vector<int> a, b;
  cin >> n >> dx >> dy;
  for (int i = 0; i < n; ++i) {
    int x, y;
    cin >> x >> y;
    a.push_back(x);
    b.push_back(y);
  }
  cin.close();
  long long ans_x = calc(a, dx);
  memset(cate, 0, N * sizeof(int));
  memset(sum, 0, N * sizeof(long long));
  long long ans_y = calc(b, dy);
  cout << ans_x + ans_y << "\n";
  cout.close();
  return 0;
}