結果

問題 No.3281 Pacific White-sided Dolphin vs Monster
ユーザー hirayuu_yc
提出日時 2025-10-04 10:57:57
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 1,289 bytes
コンパイル時間 341 ms
コンパイル使用メモリ 82,088 KB
実行使用メモリ 729,320 KB
最終ジャッジ日時 2025-10-04 10:58:03
合計ジャッジ時間 5,311 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 15 MLE * 1 -- * 35
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
import heapq

def can_finish(H, t, powers):
    """Return True if we can finish all monsters with t attacks.
       We assume `powers` is a list of 2^k values for k=0..(max_needed-1).
    """
    if t == 0:
        return all(h <= 0 for h in H)
    # heap of negatives for max-heap
    heap = [-h for h in H if h > 0]
    if not heap:
        return True
    heapq.heapify(heap)
    # use largest powers first: powers[t-1], ..., powers[0]
    for k in range(t - 1, -1, -1):
        if not heap:
            return True
        largest = -heapq.heappop(heap)
        largest -= powers[k]
        if largest > 0:
            heapq.heappush(heap, -largest)
    return not heap

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return
    it = iter(data)
    n = int(next(it))
    H = [int(next(it)) for _ in range(n)]

    # safe upper bound: N + 60 (2^60 >= 1e18)
    MAX_EXTRA = 60
    hi_bound = n + MAX_EXTRA

    # Precompute powers 2^0 ... 2^(hi_bound-1)
    powers = [1 << i for i in range(hi_bound)]

    lo, hi = 0, hi_bound
    while lo < hi:
        mid = (lo + hi) // 2
        if can_finish(H, mid, powers):
            hi = mid
        else:
            lo = mid + 1
    print(lo)

if __name__ == "__main__":
    main()
0