結果
問題 | No.771 しおり |
ユーザー |
|
提出日時 | 2022-10-23 16:00:08 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,280 ms / 2,000 ms |
コード長 | 1,072 bytes |
コンパイル時間 | 259 ms |
コンパイル使用メモリ | 82,284 KB |
実行使用メモリ | 132,920 KB |
最終ジャッジ日時 | 2024-07-22 07:32:58 |
合計ジャッジ時間 | 17,382 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 43 |
ソースコード
import sysreadline = sys.stdin.readlineN = int(readline())A = [0] * NB = [0] * Nfor i in range(N):A[i], B[i] = map(int,readline().split())# dp[S][v] = 並べた本の集合がSで、一番右にある本がvのときの醜さINF = 1 << 60dp = [[INF] * N for i in range(1 << N)]# まず最初の一冊を選ぶfor i in range(N):dp[1 << i][i] = 0 # まだ醜さが定義されていない状態for status in range(1, 1 << N): # 0の状態は考えないfor v in range(N): # 最後の本if (status >> v) & 1 == 0:continuefor target in range(N): # 次に置く本if (status >> target) & 1:continue # 既に置いてる# 本の厚さBi、表紙からの厚さAi# 今置かれている本に残っているしおりからの間隔はB[v] - A[v]# 次に置く本のしおりまでの間隔はA[target]gap = max(dp[status][v], B[v] - A[v] + A[target])next_status = status | (1 << target)if dp[next_status][target] > gap:dp[next_status][target] = gapprint(min(dp[-1]))