結果
問題 | No.974 最後の日までに |
ユーザー |
![]() |
提出日時 | 2020-04-01 01:24:50 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 142 ms / 2,000 ms |
コード長 | 1,268 bytes |
コンパイル時間 | 142 ms |
コンパイル使用メモリ | 12,800 KB |
実行使用メモリ | 19,328 KB |
最終ジャッジ日時 | 2024-06-25 15:54:37 |
合計ジャッジ時間 | 3,919 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 49 |
ソースコード
#!/usr/bin/ python3.8import sysread = sys.stdin.buffer.readreadline = sys.stdin.buffer.readlinereadlines = sys.stdin.buffer.readlinesW = int(readline())m = map(int, read().split())ABC = tuple(zip(m, m, m))def drop(P):P.sort()Q = []for x, y in P:while Q and Q[-1][0] <= x and Q[-1][1] <= y:Q.pop()Q.append((x, y))return Qdef gen_all_patterns(L, R):"""L 日目約束なしの状態から、R日目約束なしの状態へ"""n = R - Ldp = [[] for _ in range(n + 1)]dp[0] = [(0,0)]for i, (a, b, c) in enumerate(ABC[L:R]):dp[i] = drop(dp[i])dp[i + 1] += [(x+a,y) for x,y in dp[i]]if i:dp[i + 1] += [(x-c,y+b) for x,y in dp[i - 1]]return drop(dp[-1])def solve(n):""" n日目約束なしを経由するパターンを解く """P = gen_all_patterns(0, n)[::-1]Q = gen_all_patterns(n, W)[::-1]ret = 0for qx, qy in Q:while P and P[-1][0] + qx < 0:P.pop()if not P:return retx = P[-1][1] + qyif ret < x:ret = xreturn retanswer = 0for n in range(W // 2, W // 2 + 2):x = solve(n)if answer < x:answer = xprint(answer)