結果

問題 No.1045 直方体大学
ユーザー lam6er
提出日時 2025-04-15 23:32:10
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 445 ms / 2,000 ms
コード長 1,602 bytes
コンパイル時間 196 ms
コンパイル使用メモリ 81,788 KB
実行使用メモリ 109,880 KB
最終ジャッジ日時 2025-04-15 23:33:21
合計ジャッジ時間 4,965 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import defaultdict

def generate_options(a, b, c):
    options = []
    pairs = [
        (max(a, b), min(a, b), c),
        (max(a, c), min(a, c), b),
        (max(b, c), min(b, c), a),
    ]
    seen = set()
    for x, y, h in pairs:
        if (x, y) not in seen:
            seen.add((x, y))
            options.append((x, y, h))
    return options

n = int(input())
prisms = []
for _ in range(n):
    a, b, c = map(int, input().split())
    prisms.append(generate_options(a, b, c))

# Initialize DP: each mask has a dictionary of (x, y) -> max_height
dp = [defaultdict(int) for _ in range(1 << n)]

# Process masks in order of increasing number of set bits
for mask in sorted(range(1 << n), key=lambda x: bin(x).count('1')):
    current_dp = dp[mask]
    for i in range(n):
        if not (mask & (1 << i)):
            for a, b, h in prisms[i]:
                if mask == 0:
                    new_mask = mask | (1 << i)
                    if dp[new_mask][(a, b)] < h:
                        dp[new_mask][(a, b)] = h
                else:
                    for (x_prev, y_prev), current_h in current_dp.items():
                        if a <= x_prev and b <= y_prev:
                            new_mask = mask | (1 << i)
                            new_h = current_h + h
                            if dp[new_mask][(a, b)] < new_h:
                                dp[new_mask][(a, b)] = new_h

max_height = 0
for mask in range(1 << n):
    current_max = max(dp[mask].values(), default=0)
    if current_max > max_height:
        max_height = current_max

print(max_height)
0