結果
問題 |
No.1739 Princess vs. Dragoness (& AoE)
|
ユーザー |
![]() |
提出日時 | 2025-06-11 00:47:57 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,513 ms / 3,000 ms |
コード長 | 1,160 bytes |
コンパイル時間 | 486 ms |
コンパイル使用メモリ | 82,336 KB |
実行使用メモリ | 123,460 KB |
最終ジャッジ日時 | 2025-06-11 00:48:21 |
合計ジャッジ時間 | 23,876 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 40 |
ソースコード
from heapq import heappush, heappop, heapify def bsearch(low: int, high: int, fun, is_complement=False) -> int: def pred(x: int) -> bool: return not fun(x) if is_complement else fun(x) lo = low hi = high res = low while lo <= hi: m = (lo + hi) // 2 if pred(m): res = max(res, m) lo = m + 1 else: hi = m - 1 return res + 1 if is_complement else res def can(m: int) -> bool: if m < 0: return False q = [] for h in H: if h-m > 0: q.append(-(h-m)) heapify(q) na = A while na > 0 and len(q) > 0: x = -heappop(q) if x <= X: na -= 1 else: d = x // X y = x - X * min(d, na) heappush(q, -y) na -= min(d, na) # for _ in range(A): # if len(q) == 0: break # x = -heappop(q) # if x > X: # heappush(q, -(x-X)) tot = sum(-x for x in q) return tot <= Y * B N, A, B, X, Y = map(int, input().split()) H = list(map(int, input().split())) ans = bsearch(-1, 10**9, can, is_complement=True) print(ans)