結果

問題 No.1739 Princess vs. Dragoness (& AoE)
コンテスト
ユーザー Shirotsume
提出日時 2021-11-05 18:42:18
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 332 ms / 3,000 ms
コード長 923 bytes
コンパイル時間 438 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 112,892 KB
最終ジャッジ日時 2024-11-25 11:15:41
合計ジャッジ時間 9,494 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

n, a, b, x, y = map(int,input().split())
h = list(map(int,input().split()))
def solve(n, a, b, x, y, h):
    h.sort()
    from collections import deque
    import heapq
    ope_list = []
    h2 = []
    for i in range(n):
        heapq.heappush(h2, (- h[i], i))
        
    for i in range(a):
        now, nowi = heapq.heappop(h2)
        now = min(0, now + x)
        heapq.heappush(h2, (now, nowi))
        ope_list.append(nowi)
    def check(k):
        h2 = [0] * n
        for i in range(n):
            h2[i] = max(0, h[i] - k)
        for i in range(a):
            h2[ope_list[i]] = max(0, h2[ope_list[i]] - x)
        if sum(h2) <= b * y:
            return True
        else:
            return False

    ok = 10 ** 9
    ng = -1

    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        if check(mid):
            ok = mid
        else:
            ng = mid
    return ok
print(solve(n, a, b, x, y, h))
0