Cod sursa(job #2900605)

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

using namespace std;

const int N = 5e4 + 5;

int cate_st[N], cate_dr[N];
long long sum_st[N], sum_dr[N];

long long calc(vector<int>& v, const int d) {
  memset(cate_st, 0, N * sizeof(int));
  memset(cate_dr, 0, N * sizeof(int));
  memset(sum_st, 0, N * sizeof(long long));
  memset(sum_dr, 0, N * sizeof(long long));
  for (auto i: v) {
    ++cate_st[i], sum_st[i] += i;
    ++cate_dr[i], sum_dr[i] += i;
  }
  for (int i = 1; i < N; ++i) {
    cate_st[i] += cate_st[i - 1];
    sum_st[i] += sum_st[i - 1];
  }
  for (int i = N - 2; i >= 0; --i) {
    cate_dr[i] += cate_dr[i + 1];
    sum_dr[i] += sum_dr[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_st[i - 1] * i - sum_st[i - 1];
    if (i + d < N)
      add_dr = sum_dr[i + d] - 1LL * cate_dr[i + d] * (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();
  cout << calc(a, dx) + calc(b, dy) << "\n";
  cout.close();
  return 0;
}