Cod sursa(job #1490951)

Utilizator vladrochianVlad Rochian vladrochian Data 24 septembrie 2015 15:25:19
Problema Tribute Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.72 kb
#include <fstream>
#include <algorithm>
using namespace std;

const int kMaxN = 50005;

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

int N, DX, DY;
int x[kMaxN], y[kMaxN];

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

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