結果
問題 | No.1045 直方体大学 |
ユーザー |
![]() |
提出日時 | 2023-02-13 23:46:47 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,023 bytes |
コンパイル時間 | 846 ms |
コンパイル使用メモリ | 82,188 KB |
実行使用メモリ | 108,496 KB |
最終ジャッジ日時 | 2024-07-16 13:54:54 |
合計ジャッジ時間 | 22,225 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 10 TLE * 7 |
ソースコード
N = int(input())D = []for i in range(N):D.append(list(map(int, input().split())))N2 = 1 << Ninf = 10 ** 18dp = [[-inf] * (N * 3) for i in range(N2)]ans = 0for i in range(N):for k in range(3):dp[1 << i][i * 3 + k] = D[i][k]ans = max(ans, dp[1 << i][i * 3 + k])def check(i, j, a, b):if D[i][(a + 1) % 3] <= D[j][(b + 1) % 3] and D[i][(a + 2) % 3] <= D[j][(b + 2) % 3]:return Trueif D[i][(a + 2) % 3] <= D[j][(b + 1) % 3] and D[i][(a + 1) % 3] <= D[j][(b + 2) % 3]:return Truereturn Falsefor s in range(1, N2):for p in range(3 * N):q, r = divmod(p, 3)if (s >> q) & 1 == 0:continuefor i in range(N):if (s >> i) & 1:continuefor k in range(3):if check(q, i, r, k):dp[s | (1 << i)][3 * i + k] = max(dp[s | (1 << i)][3 * i + k], dp[s][p] + D[i][k])ans = max(ans, dp[s | (1 << i)][3 * i + k])print(ans)