結果
問題 |
No.1045 直方体大学
|
ユーザー |
![]() |
提出日時 | 2024-08-15 04:09:47 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 774 ms / 2,000 ms |
コード長 | 1,306 bytes |
コンパイル時間 | 415 ms |
コンパイル使用メモリ | 82,824 KB |
実行使用メモリ | 151,088 KB |
最終ジャッジ日時 | 2024-08-15 04:09:58 |
合計ジャッジ時間 | 8,810 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 17 |
ソースコード
N=int(input()) ABC=[] for i in range(N): a,b,c=map(int,input().split()) ABC.append((a,b,c)) def idx(bit,i,x,y): return ((bit*N+i)*3+x)*3+y trans=[[] for ij in range(N*N)] for i in range(N): for j in range(N): if i==j: continue for x0 in range(3): for y0 in range(x0+1,3): if x0==y0: continue for x1 in range(3): for y1 in range(x1+1,3): if x1==y1: continue if ABC[i][x0]>=ABC[j][x1] and ABC[i][y0]>=ABC[j][y1] or ABC[i][x0]>=ABC[j][y1] and ABC[i][y0]>=ABC[j][x1]: trans[i*N+j].append((x0,y0,x1,y1,ABC[j][3-x1-y1])) inf=1<<30 dp=[-inf]*((9*N)<<N) for bit in range(1,1<<N): I=[i for i in range(N) if bit&1<<i] if len(I)==1: for x in range(3): for y in range(3): if x==y: continue dp[idx(bit,I[0],x,y)]=ABC[I[0]][3-x-y] else: for i in I: for j in I: if i==j: continue for x0,y0,x1,y1,h in trans[i*N+j]: dp[idx(bit,j,x1,y1)]=max(dp[idx(bit,j,x1,y1)],dp[idx(bit^1<<j,i,x0,y0)]+h) ans=max(dp) print(ans)