結果

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

ソースコード

diff # 

import sys
import heapq

def can_finish(H, t):
    # Use powers 2^{t-1}, 2^{t-2}, ..., 2^0 and greedily assign largest power to largest remaining HP.
    if t == 0:
        return all(h <= 0 for h in H)
    heap = [-h for h in H if h > 0]
    heapq.heapify(heap)
    for k in range(t - 1, -1, -1):
        if not heap:
            return True
        largest = -heapq.heappop(heap)
        largest -= (1 << k)
        if largest > 0:
            heapq.heappush(heap, -largest)
    return not heap

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

    # Upper bound: smallest hi with (2^hi - 1) >= sum(H)
    total = sum(H)
    hi = 0
    # increase hi until sum of powers 1+2+...+2^{hi-1} = 2^hi - 1 >= total
    # hi won't be large (<= ~100), Python handles big ints well.
    while (1 << hi) - 1 < total:
        hi += 1

    lo = 0
    # binary search minimal t in [0, hi]
    while lo < hi:
        mid = (lo + hi) // 2
        if can_finish(H, mid):
            hi = mid
        else:
            lo = mid + 1
    print(lo)

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