結果
問題 | No.771 しおり |
ユーザー |
|
提出日時 | 2021-01-30 12:22:30 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,039 ms / 2,000 ms |
コード長 | 663 bytes |
コンパイル時間 | 171 ms |
コンパイル使用メモリ | 82,308 KB |
実行使用メモリ | 113,136 KB |
最終ジャッジ日時 | 2024-07-22 07:26:32 |
合計ジャッジ時間 | 15,070 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 43 |
ソースコード
N = int(input())Books = [tuple(map(int, input().split())) for _ in range(N)]adj = [[0] * N for _ in range(N)]for i, (ai, bi) in enumerate(Books):for j, (aj, bj) in enumerate(Books):adj[i][j] = bi - ai + ajINF = 20000dp = [[INF] * (1 << N) for _ in range(N)]for i in range(N):for j in range(N):dp[i][1 << j] = 0for b in range(1, 1 << N):for i in range(N):if not b & (1 << i):continuefor j in range(N):if b & (1 << j):continuedp[j][b | (1 << j)] = min(dp[j][b | (1 << j)], max(dp[i][b], adj[i][j]))ans = min(dp[i][-1] for i in range(N))print(ans)