結果
問題 | No.1045 直方体大学 |
ユーザー | pekempey |
提出日時 | 2020-05-01 22:49:54 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,378 bytes |
コンパイル時間 | 330 ms |
コンパイル使用メモリ | 86,984 KB |
実行使用メモリ | 109,256 KB |
最終ジャッジ日時 | 2023-08-26 15:32:47 |
合計ジャッジ時間 | 25,397 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 74 ms
71,252 KB |
testcase_01 | AC | 74 ms
71,372 KB |
testcase_02 | AC | 90 ms
76,496 KB |
testcase_03 | AC | 90 ms
76,404 KB |
testcase_04 | AC | 90 ms
76,584 KB |
testcase_05 | AC | 130 ms
77,856 KB |
testcase_06 | AC | 138 ms
78,144 KB |
testcase_07 | AC | 132 ms
78,168 KB |
testcase_08 | TLE | - |
testcase_09 | TLE | - |
testcase_10 | AC | 1,936 ms
108,976 KB |
testcase_11 | TLE | - |
testcase_12 | TLE | - |
testcase_13 | TLE | - |
testcase_14 | TLE | - |
testcase_15 | TLE | - |
testcase_16 | TLE | - |
testcase_17 | AC | 113 ms
77,960 KB |
testcase_18 | TLE | - |
ソースコード
def input_int(): return int(input()) def input_ints(): return list(map(int, input().split())) N = input_int() A = [] B = [] C = [] for _ in range(N): a, b, c = sorted(input_ints()) A.append(a) B.append(b) C.append(c) # 0: AB # 1: AC # 2: BC def height(k): i, j = divmod(k, 3) if j == 0: return C[i] elif j == 1: return B[i] else: return A[i] def face(k): i, j = divmod(k, 3) if j == 0: return A[i], B[i] elif j == 1: k return A[i], C[i] else: return B[i], C[i] INF = 10**9 dp = [[-INF for j in range(N * 3)] for i in range(1 << N)] for i in range(N): dp[1 << i][i * 3 + 0] = height(i * 3 + 0) dp[1 << i][i * 3 + 1] = height(i * 3 + 1) dp[1 << i][i * 3 + 2] = height(i * 3 + 2) def can(x, y): f1 = face(x) f2 = face(y) return f1[0] <= f2[0] and f1[1] <= f2[1] g = [[can(i, j) for j in range(N * 3)] for i in range(N * 3)] ans = 0 for i in range(1 << N): to = list(filter(lambda x: ~i >> x & 1, range(N))) for j in range(N * 3): if dp[i] == -INF: continue ans = max(ans, dp[i][j]) for kx in to: for ky in range(3): k = kx * 3 + ky if g[j][k]: dp[i | 1 << kx][k] = max(dp[i | 1 << kx][k], dp[i][j] + height(k)) print(ans)