結果
問題 | No.1045 直方体大学 |
ユーザー |
![]() |
提出日時 | 2024-08-15 04:07:29 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,243 bytes |
コンパイル時間 | 225 ms |
コンパイル使用メモリ | 82,432 KB |
実行使用メモリ | 156,800 KB |
最終ジャッジ日時 | 2024-08-15 04:07:46 |
合計ジャッジ時間 | 16,013 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 16 TLE * 1 |
ソースコード
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+ytrans=[[] for ij in range(N*N)]for i in range(N):for j in range(N):if i==j:continuefor x0 in range(3):for y0 in range(3):if x0==y0:continuefor x1 in range(3):for y1 in range(3):if x1==y1:continueif ABC[i][x0]>=ABC[j][x1] and ABC[i][y0]>=ABC[j][y1]:trans[i*N+j].append((x0,y0,x1,y1,ABC[j][3-x1-y1]))inf=1<<30dp=[-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:continuedp[idx(bit,I[0],x,y)]=ABC[I[0]][3-x-y]else:for i in I:for j in I:if i==j:continuefor 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)