結果
問題 | No.1045 直方体大学 |
ユーザー |
![]() |
提出日時 | 2021-05-13 12:25:57 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,813 ms / 2,000 ms |
コード長 | 1,467 bytes |
コンパイル時間 | 192 ms |
コンパイル使用メモリ | 82,416 KB |
実行使用メモリ | 107,256 KB |
最終ジャッジ日時 | 2024-09-25 01:52:15 |
合計ジャッジ時間 | 4,468 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 17 |
ソースコード
import syssys.setrecursionlimit(10**6)int1 = lambda x: int(x)-1p2D = lambda x: print(*x, sep="\n")def II(): return int(sys.stdin.buffer.readline())def LI(): return list(map(int, sys.stdin.buffer.readline().split()))def LI1(): return list(map(int1, sys.stdin.buffer.readline().split()))def LLI(rows_number): return [LI() for _ in range(rows_number)]def LLI1(rows_number): return [LI1() for _ in range(rows_number)]def BI(): return sys.stdin.buffer.readline().rstrip()def SI(): return sys.stdin.buffer.readline().rstrip().decode()# dij = [(0, 1), (-1, 0), (0, -1), (1, 0)]# dij = [(0, 1), (-1, 0), (0, -1), (1, 0), (1, 1), (1, -1), (-1, 1), (-1, -1)]dij = [(0, 1), (1, 0), (1, 1), (1, -1)]inf = 10**16# md = 998244353md = 10**9+7n = II()ihwt = []for i in range(n):a, b, c = sorted(LI())ihwt.append((i, a, b, c))ihwt.append((i, a, c, b))ihwt.append((i, b, c, a))ihwt.sort(key=lambda x: (x[1], x[2]))def chmax(s, j, val):if val > dp[s][j]: dp[s][j] = valans = 0dp = [[-1]*n*3 for _ in range(1 << n)]for j, (i, h, w, t) in enumerate(ihwt): dp[1 << i][j] = tfor s in range(1 << n):for j in range(n*3):pre = dp[s][j]if pre == -1: continueif pre > ans: ans = pre_, H, W, T = ihwt[j]for nj, (i, h, w, t) in enumerate(ihwt):if h > H: breakif w > W: continueif s >> i & 1: continuechmax(s | 1 << i, nj, pre+t)print(ans)