結果

問題 No.1045 直方体大学
コンテスト
ユーザー lam6er
提出日時 2025-03-31 17:42:55
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,633 bytes
コンパイル時間 228 ms
コンパイル使用メモリ 82,164 KB
実行使用メモリ 65,032 KB
最終ジャッジ日時 2025-03-31 17:43:47
合計ジャッジ時間 2,037 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other WA * 17
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
from collections import defaultdict

def main():
    n = int(sys.stdin.readline())
    cuboids = []
    for _ in range(n):
        a, b, c = map(int, sys.stdin.readline().split())
        opts = []
        opts.append((tuple(sorted([a, b])), c))
        opts.append((tuple(sorted([a, c])), b))
        opts.append((tuple(sorted([b, c])), a))
        cuboids.append(opts)
    
    dp = defaultdict(dict)
    
    # Initialize with each cuboid's possible orientations
    for i in range(n):
        for (base, h) in cuboids[i]:
            a, b = base
            mask = 1 << i
            if (a, b) not in dp[mask] or h > dp[mask].get((a, b), 0):
                dp[mask][(a, b)] = h
    
    # Process all masks
    for mask in list(dp.keys()):
        current_entries = list(dp[mask].items())
        for (a_prev, b_prev), current_h in current_entries:
            for i in range(n):
                if not (mask & (1 << i)):
                    for (new_base, h_new) in cuboids[i]:
                        a_new, b_new = new_base
                        if a_new <= a_prev and b_new <= b_prev:
                            new_mask = mask | (1 << i)
                            total_h = current_h + h_new
                            if (a_new, b_new) not in dp[new_mask] or dp[new_mask].get((a_new, b_new), 0) < total_h:
                                dp[new_mask][(a_new, b_new)] = total_h
    
    max_height = 0
    for mask in dp:
        for (a, b) in dp[mask]:
            if dp[mask][(a, b)] > max_height:
                max_height = dp[mask][(a, b)]
    print(max_height)

if __name__ == "__main__":
    main()
0