結果

問題 No.1045 直方体大学
ユーザー lam6er
提出日時 2025-04-15 23:37:03
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 581 ms / 2,000 ms
コード長 2,440 bytes
コンパイル時間 347 ms
コンパイル使用メモリ 81,768 KB
実行使用メモリ 114,964 KB
最終ジャッジ日時 2025-04-15 23:37:51
合計ジャッジ時間 4,378 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx])
    idx += 1
    
    cuboids = []
    for _ in range(N):
        A = int(input[idx])
        B = int(input[idx+1])
        C = int(input[idx+2])
        idx +=3
        perms = [(A,B,C), (A,C,B), (B,A,C), (B,C,A), (C,A,B), (C,B,A)]
        configs = []
        for p in perms:
            a, b, c = p
            sorted_lw = sorted([a, b], reverse=True)
            l, w = sorted_lw
            h = c
            configs.append((l, w, h))
        cuboids.append(configs)
    
    all_configs = []
    for i in range(N):
        for (l, w, h) in cuboids[i]:
            all_configs.append((l, w, h, i))
    
    from collections import defaultdict
    dp = defaultdict(list)
    
    def add_entry(entries, new_entry):
        l_new, w_new, sum_new = new_entry
        for (l, w, s) in entries:
            if l >= l_new and w >= w_new and s >= sum_new:
                return False
        new_entries = []
        for (l, w, s) in entries:
            if not (l <= l_new and w <= w_new and s <= sum_new):
                new_entries.append((l, w, s))
        new_entries.append((l_new, w_new, sum_new))
        new_entries.sort(key=lambda x: (-x[0], -x[1], -x[2]))
        entries[:] = new_entries
        return True
    
    for (l, w, h, i) in all_configs:
        mask = 1 << i
        entry = (l, w, h)
        if not dp[mask]:
            dp[mask] = []
        add_entry(dp[mask], entry)
    
    processed_masks = set(dp.keys())
    queue = list(dp.keys())
    
    for mask in queue:
        entries = dp[mask]
        for (l_j, w_j, h_j, j) in all_configs:
            if (mask & (1 << j)) != 0:
                continue
            new_mask = mask | (1 << j)
            added = False
            for (l_prev, w_prev, sum_prev) in entries:
                if l_prev >= l_j and w_prev >= w_j:
                    new_sum = sum_prev + h_j
                    new_entry = (l_j, w_j, new_sum)
                    if add_entry(dp[new_mask], new_entry):
                        added = True
            if added and new_mask not in processed_masks:
                processed_masks.add(new_mask)
                queue.append(new_mask)
    
    max_sum = 0
    for entries in dp.values():
        for (l, w, s) in entries:
            if s > max_sum:
                max_sum = s
    print(max_sum)

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