結果
問題 | No.54 Happy Hallowe'en |
ユーザー |
|
提出日時 | 2015-08-02 18:18:40 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 113 ms / 5,000 ms |
コード長 | 1,565 bytes |
コンパイル時間 | 100 ms |
コンパイル使用メモリ | 12,672 KB |
実行使用メモリ | 15,488 KB |
最終ジャッジ日時 | 2024-10-15 17:13:17 |
合計ジャッジ時間 | 1,798 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 19 |
ソースコード
import syssys.setrecursionlimit(1000000)def read_data():N = int(input())VT = []for n in range(N):v, t = map(int, input().split())VT.append((v + t, v, t))return N, VTdef solve(N, VT):VT.sort(reverse=True)candidate = min(VT[0][0] - 1, sum(v for vt, v, t in VT))while not is_valid(candidate, VT):candidate -= 1return candidatedef is_valid(val, VT):head = 0nexts = list(range(1, len(VT) + 1))prevs = list(range(-1, len(VT) - 1))lower = valupper = float('inf')return dfs(lower, upper, VT, head, nexts, prevs)def dfs(lower, upper, VT, head, nexts, prevs):'''VTのうち、used でないものを使って、lower 以上、upper 未満の選び方をできるかを返す。'''if lower == 0:return Trueif lower < 0:return Falsei = headend = len(VT)while i != end:val, v, t = VT[i]if v >= upper:i = nexts[i]continueif val < lower:return Falseif i == head:nhead = nexts[i]else:nhead = headnexts[prevs[i]] = nexts[i]if nexts[i] != end:prevs[nexts[i]] = prevs[i]result = dfs(lower - v, min(upper, t), VT, nhead, nexts, prevs)if i != head:nexts[prevs[i]] = iif nexts[i] != end:prevs[nexts[i]] = iif result:return Truei = nexts[i]return FalseN, VT = read_data()print(solve(N, VT))