結果
問題 | No.1045 直方体大学 |
ユーザー | maspy |
提出日時 | 2020-05-01 21:51:04 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,490 ms / 2,000 ms |
コード長 | 1,085 bytes |
コンパイル時間 | 564 ms |
コンパイル使用メモリ | 86,588 KB |
実行使用メモリ | 109,640 KB |
最終ジャッジ日時 | 2023-08-26 09:16:26 |
合計ジャッジ時間 | 6,121 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 62 ms
70,908 KB |
testcase_01 | AC | 64 ms
70,948 KB |
testcase_02 | AC | 83 ms
75,808 KB |
testcase_03 | AC | 64 ms
71,228 KB |
testcase_04 | AC | 69 ms
75,680 KB |
testcase_05 | AC | 83 ms
76,268 KB |
testcase_06 | AC | 81 ms
76,700 KB |
testcase_07 | AC | 80 ms
76,552 KB |
testcase_08 | AC | 183 ms
109,456 KB |
testcase_09 | AC | 162 ms
109,284 KB |
testcase_10 | AC | 165 ms
109,196 KB |
testcase_11 | AC | 189 ms
109,348 KB |
testcase_12 | AC | 198 ms
109,388 KB |
testcase_13 | AC | 201 ms
109,488 KB |
testcase_14 | AC | 174 ms
109,504 KB |
testcase_15 | AC | 222 ms
109,444 KB |
testcase_16 | AC | 266 ms
109,640 KB |
testcase_17 | AC | 79 ms
76,680 KB |
testcase_18 | AC | 1,490 ms
109,516 KB |
ソースコード
import sys import itertools read = sys.stdin.buffer.read readline = sys.stdin.buffer.readline readlines = sys.stdin.buffer.readlines INF = 10**18 N = int(readline()) m = map(int, read().split()) ABC = list(zip(m, m, m)) pattern = [None] * (3 * N) for i in range(N): a, b, c = sorted(ABC[i]) pattern[3 * i] = (a, b, c) pattern[3 * i + 1] = (b, c, a) pattern[3 * i + 2] = (a, c, b) dp = [[-INF] * (3 * N) for _ in range(1 << N)] for i in range(N): for k in range(3): dp[1 << i][3 * i + k] = pattern[3 * i + k][2] for s in range(1 << N): for p in range(3*N): if dp[s][p] == -INF: continue for q in range(3*N): i = q // 3 if s & (1 << i): continue t = s ^ (1 << i) a1, b1, c1 = pattern[p] a2, b2, c2 = pattern[q] if a1 > a2: continue if b1 > b2: continue x = dp[s][p] + c2 if dp[t][q] < x: dp[t][q] = x answer = max(itertools.chain(*dp)) print(answer)