結果

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

ソースコード

diff # 

import sys
from collections import defaultdict

def main():
    n = int(sys.stdin.readline())
    data = [tuple(map(int, sys.stdin.readline().split())) for _ in range(n)]
    
    # Preprocess each block's possible base options (x, y) in descending order, and the corresponding height
    blocks = []
    for a, b, c in data:
        # Generate all three possible base orientations
        options = [
            (max(a, b), min(a, b), c),
            (max(a, c), min(a, c), b),
            (max(b, c), min(b, c), a)
        ]
        blocks.append(options)
    
    dp = defaultdict(dict)
    max_total = 0
    
    # Initialize DP for masks with single blocks
    for i in range(n):
        for x, y, h in blocks[i]:
            mask = 1 << i
            key = (x, y)
            if key not in dp[mask] or dp[mask][key] < h:
                dp[mask][key] = h
                if h > max_total:
                    max_total = h
    
    # Generate mask processing order based on the number of bits set (ascending)
    mask_order = []
    for mask in dp.keys():
        cnt = bin(mask).count('1')
        mask_order.append((cnt, mask))
    mask_order.sort()
    
    # Process each mask in the order of increasing bit count
    for cnt, mask in mask_order:
        current_entries = list(dp[mask].items())
        for (x_prev, y_prev), total_prev in current_entries:
            # Try adding each unused block
            for i in range(n):
                if (mask & (1 << i)) != 0:
                    continue  # block i is already used
                # Check all base options of block i
                for x_new, y_new, h_new in blocks[i]:
                    if x_new <= x_prev and y_new <= y_prev:
                        new_mask = mask | (1 << i)
                        new_total = total_prev + h_new
                        key_new = (x_new, y_new)
                        # Update the new_mask's entry if this is better
                        if key_new not in dp[new_mask] or dp[new_mask][key_new] < new_total:
                            dp[new_mask][key_new] = new_total
                            if new_total > max_total:
                                max_total = new_total
    
    print(max_total)

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