第八回 アルゴリズム実技検定 G問題

PAST008G

Binary search で \(K\)-th を求める．
\(P(x) := \) ((\(x\) 以下の個数) \(\geq K\) )
とすると， \(P\) は \(x\) に対して単調．

使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"

int main() {

  ll n,k;

  cin >> n >> k;

  vll a(n), b(n), c(n);

  rep(i,n) cin >> a[i] >> b[i] >> c[i];

  ll ok, ng;

  ng = 0, ok = 4e18;

  while(abs(ok-ng) > 1){

    ll md = (ok + ng)/2;

    ll cnt = 0;

    rep(i,n){

      if(md >= b[i]){

        cnt += min(1+(md-b[i])/c[i], a[i]);

      }

    }

    if(cnt >= k) ok = md;

    else ng = md;

  }

  cout << ok << endl;

  return 0;

}