結果
問題 |
No.1045 直方体大学
|
ユーザー |
|
提出日時 | 2022-03-27 22:47:24 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,245 ms / 2,000 ms |
コード長 | 1,212 bytes |
コンパイル時間 | 302 ms |
コンパイル使用メモリ | 82,112 KB |
実行使用メモリ | 184,036 KB |
最終ジャッジ日時 | 2024-11-06 15:21:59 |
合計ジャッジ時間 | 7,798 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 17 |
ソースコード
n = int(input()) ABC = [list(map(int,input().split())) for i in range(n)] dp = [[[0]*3 for i in range(n)] for j in range(1<<n)] for i,(a,b,c) in enumerate(ABC): dp[1<<i][i][0] = c dp[1<<i][i][1] = b dp[1<<i][i][2] = a ans = 0 for bit in range(1<<n): for j in range(n): a,b,c = ABC[j] for k in range(3): h = dp[bit][j][k] ans = max(ans,h) if h == 0: continue for t in range(n): if bit >> t & 1: continue if k == 0: x,y = a,b elif k == 1: x,y = a,c else: x,y = b,c na,nb,nc = ABC[t] if (na <= x and nb <= y) or (na <= y and nb <= x): dp[bit|1<<t][t][0] = max(dp[bit|1<<t][t][0],h+nc) if (na <= x and nc <= y) or (na <= y and nc <= x): dp[bit|1<<t][t][1] = max(dp[bit|1<<t][t][1],h+nb) if (nb <= x and nc <= y) or (nb <= y and nc <= x): dp[bit|1<<t][t][2] = max(dp[bit|1<<t][t][2],h+na) print(ans)