convex/monge/alien.hpp

View this file on GitHub
Last update: 2026-05-31 19:49:15+09:00
Include: #include "convex/monge/alien.hpp"

Code

// T は整数型を仮定
// solve(penalty, minimize_cnt)
// lo: cnt > K, hi: cnt<=K
template <typename T, typename F>
T alien_trick(int K, T lo, T hi, F solve) {
  while (lo + 1 < hi) {
    T mid = (lo + hi) / 2;
    auto [val, cnt] = solve(mid, true);
    if (cnt <= K) {
      hi = mid;
    } else {
      lo = mid;
    }
  }

  auto [val, cnt] = solve(hi, true);
  return val - hi * K;
}

#line 1 "convex/monge/alien.hpp"
// T は整数型を仮定
// solve(penalty, minimize_cnt)
// lo: cnt > K, hi: cnt<=K
template <typename T, typename F>
T alien_trick(int K, T lo, T hi, F solve) {
  while (lo + 1 < hi) {
    T mid = (lo + hi) / 2;
    auto [val, cnt] = solve(mid, true);
    if (cnt <= K) {
      hi = mid;
    } else {
      lo = mid;
    }
  }

  auto [val, cnt] = solve(hi, true);
  return val - hi * K;
}