結果

問題 No.1045 直方体大学
ユーザー convexineq
提出日時 2020-05-01 23:18:46
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,777 ms / 2,000 ms
コード長 747 bytes
コンパイル時間 233 ms
コンパイル使用メモリ 82,432 KB
実行使用メモリ 101,504 KB
最終ジャッジ日時 2024-12-25 14:21:35
合計ジャッジ時間 17,939 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

# coding: utf-8
# Your code here!
import sys
readline = sys.stdin.readline
read = sys.stdin.read

#n,m,s = [int(i) for i in readline().split()]
n = int(input())
res = [[int(i) for i in readline().split()] for _ in range(n)]

abc = [(0,0,0,100)]
for i,x in enumerate(res):
    a,b,c = sorted(x)
    abc.append((a,b,c,i))
    abc.append((a,c,b,i))
    abc.append((b,c,a,i))

abc.sort()

N = 1<<n
dp = [[0]*N for _ in range(3*n+1)]

for j in range(3*n+1):
    b = abc[j][1]
    for u in range(N):
        for k in range(j+1,3*n+1):
            if b <= abc[k][1] and (u>>abc[k][3])&1==0:
                nu = u|(1<<abc[k][3])
                dp[k][nu] = max(dp[k][nu],dp[j][u]+abc[k][2])

#print(abc)
#print(dp)
print(max(max(i) for i in dp))
0