結果

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

ソースコード

diff # 

def generate_combinations(a, b, c):
    combs = []
    l = max(a, b)
    s = min(a, b)
    combs.append((l, s, c))
    l = max(a, c)
    s = min(a, c)
    combs.append((l, s, b))
    l = max(b, c)
    s = min(b, c)
    combs.append((l, s, a))
    return combs

def filter_dominated(d):
    items = list(d.items())
    items.sort(key=lambda x: (-x[0][0], -x[0][1]))
    filtered = []
    for (l, s), h in items:
        dominated = False
        for (fl, fs), fh in filtered:
            if fl >= l and fs >= s and fh >= h:
                dominated = True
                break
        if not dominated:
            new_filtered = []
            for (fl, fs), fh in filtered:
                if not (l >= fl and s >= fs and h >= fh):
                    new_filtered.append(((fl, fs), fh))
            new_filtered.append(((l, s), h))
            filtered = new_filtered
    new_d = {}
    for (l, s), h in filtered:
        new_d[(l, s)] = h
    return new_d

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx])
    idx += 1
    cubes = []
    for _ in range(N):
        a, b, c = map(int, input[idx:idx+3])
        idx +=3
        cubes.append(generate_combinations(a, b, c))
    
    max_mask = 1 << N
    dp = [{} for _ in range(max_mask)]
    
    for i in range(N):
        for l, s, h in cubes[i]:
            mask = 1 << i
            key = (l, s)
            if key not in dp[mask] or dp[mask][key] < h:
                dp[mask][key] = h
    
    for mask in range(max_mask):
        dp[mask] = filter_dominated(dp[mask])
    
    for mask in range(max_mask):
        current_dict = dp[mask]
        if not current_dict:
            continue
        for j in range(N):
            if not (mask & (1 << j)):
                for lj, sj, hj in cubes[j]:
                    if mask == 0:
                        new_mask = mask | (1 << j)
                        new_h = hj
                        key = (lj, sj)
                        if key not in dp[new_mask] or dp[new_mask][key] < new_h:
                            dp[new_mask][key] = new_h
                    else:
                        for (l, s), current_h in current_dict.items():
                            if lj <= l and sj <= s:
                                new_mask = mask | (1 << j)
                                new_key = (lj, sj)
                                new_h_total = current_h + hj
                                if new_key not in dp[new_mask] or dp[new_mask][new_key] < new_h_total:
                                    dp[new_mask][new_key] = new_h_total
    
    for mask in range(max_mask):
        dp[mask] = filter_dominated(dp[mask])
    
    max_height = 0
    for mask in range(max_mask):
        for h in dp[mask].values():
            if h > max_height:
                max_height = h
    print(max_height)

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