結果
問題 | No.1739 Princess vs. Dragoness (& AoE) |
ユーザー |
|
提出日時 | 2021-11-12 22:45:36 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,694 bytes |
コンパイル時間 | 182 ms |
コンパイル使用メモリ | 12,800 KB |
実行使用メモリ | 57,520 KB |
最終ジャッジ日時 | 2024-11-25 20:28:07 |
合計ジャッジ時間 | 96,573 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 19 TLE * 21 |
ソースコード
# region templateimport sysimport typingfrom typing import Callable, Dict, List, Set, Tupleimport heapqfrom operator import itemgettersys.setrecursionlimit(10 ** 6)Vec = List[int]VecVec = List[Vec]sinput: Callable[..., str] = sys.stdin.readlineMOD: int = 1000000007INF: float = float("Inf")IINF: int = sys.maxsize# endregiondef meguru_bisect(ok: int, ng: int, is_ok: Callable[..., bool], *args) -> int:"""二分探索法Args:ok (int): is_okを満たす初期値ng (int): is_okを満たさない初期値is_ok (typing.Callable[..., bool]): 判定用関数*args (object): is_okに渡される引数Returns:int: is_okを満たす最大/小の整数"""assert is_ok(ok, *args)assert not is_ok(ng, *args)while abs(ok - ng) > 1:mid = (ok + ng) >> 1if is_ok(mid, *args):ok = midelse:ng = midreturn okdef main() -> None:n, a, b, x, y = map(int, sinput().split())h = tuple(map(int, sinput().split()))def ok(th: int) -> bool:if th < 0:return Falserem_b = y * bque = [(-h[i] + th, i) for i in range(n)]heapq.heapify(que)for _ in range(a):top, i = heapq.heappop(que)top += xheapq.heappush(que, (top, i))que.sort(key=itemgetter(1))for hi, _ in que:hi *= -1if hi >= 0:if hi > rem_b:return Falseelse:rem_b -= hireturn Trueprint(meguru_bisect(max(h), -1, ok))if __name__ == "__main__":main()