結果

問題 No.3281 Pacific White-sided Dolphin vs Monster
コンテスト
ユーザー navel_tos
提出日時 2025-09-27 11:27:36
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 94 ms / 2,000 ms
コード長 1,082 bytes
コンパイル時間 155 ms
コンパイル使用メモリ 82,708 KB
実行使用メモリ 89,728 KB
最終ジャッジ日時 2025-10-03 17:38:07
合計ジャッジ時間 4,675 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 51
権限があれば一括ダウンロードができます

ソースコード

diff # 

#yukicoder3281 Pacific White-sided Dolphin vs Monster

def main():
    import heapq
    input = __import__('sys').stdin.readline

    #入力受取  Hは正負反転のうえ、絶対値の大きい方から60要素のみ抽出
    N = int(input())
    if N <= 60:
        H = [- int(v) for v in input().split()]
        heapq.heapify(H)
    else:
        H = [0] * 60
        for i, v in enumerate(input().split()):
            if i < 60:
                H[i] = - int(v)
                if i == 59:
                    heapq.heapify(H)
            else:
                heapq.heappushpop(H, - int(v))
    n = len(H)

    #部分問題: n体のモンスターを全滅させるのに必要な最小ターン数は？
    ok, ng = n + 60, n - 1
    while abs(ok - ng) > 1:
        mid = (ok + ng) >> 1
        Q = H[:]
        p = 1 << mid
        while (p := p >> 1):
            heapq.heapreplace(Q, Q[0] + p)
            if Q[0] >= 0:
                ok = mid
                break
        else:
            ng = mid
        
    #答えを出力
    print(ok + (N - n))


main()
0