Submission #30844982

---

Source Code Expand

n = int(input())
h = [0] * n
s = [0] * n
for i in range(n):
    h[i], s[i] = map(int, input().split())
ok = 10 ** 14 # どんな順番でもスコアは max{h} + n max{s} 以下
ng = -1
while ok - ng > 1: # log_2(max{h} + n max{s}) 回実行される
    m = (ok + ng) // 2
    t = [0] * n # 風船 i は 時刻 t[i] までに割らなければならない
    for i in range(n):
        if m < h[i]: # 負の数の割り算を避ける
            t[i] = -1
        else:
            t[i] = (m - h[i]) // s[i]
    t = sorted(t) # 締め切りが早い方から割るために O(n log n) でソート
    is_ok = 1
    for i in range(n):
        if t[i] < i: # 時刻 i に割る風船の締め切り時刻 t[i] をチェック
            is_ok = 0
    if is_ok == 1:
        ok = m
    else:
        ng = m
print(ok)

Submission Info

Judge Result