結果

問題 No.15 カタログショッピング
コンテスト
ユーザー yuushi narazaki
提出日時 2025-02-28 15:53:46
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 138 ms / 5,000 ms
コード長 1,208 bytes
コンパイル時間 336 ms
コンパイル使用メモリ 82,360 KB
実行使用メモリ 103,656 KB
最終ジャッジ日時 2025-02-28 15:53:48
合計ジャッジ時間 1,787 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 10
権限があれば一括ダウンロードができます

ソースコード

diff # 

N, S = map(int, input().split())
cost = [int(input()) for _ in range(N)]

half = N // 2
left = cost[:half]
right = cost[half:]

left_sums = {}
right_sums = {}

# 左半分の部分和を求める
for i in range(2**len(left)):
    cost_l = 0
    use = []
    for j in range(len(left)):
        if (i >> j) & 1:
            cost_l += left[j]
            use.append(j + 1)
    if cost_l not in left_sums:
        left_sums[cost_l] = []
    left_sums[cost_l].append(use)

# 右半分の部分和を求める
for i in range(2**len(right)):
    cost_r = 0
    use = []
    for j in range(len(right)):
        if (i >> j) & 1:
            cost_r += right[j]
            use.append(j + 1 + len(left))
    if cost_r not in right_sums:
        right_sums[cost_r] = []
    right_sums[cost_r].append(use)

# すべての組み合わせを格納するリスト
answers = []

# 左右の部分和を組み合わせる
for x in left_sums:
    if S - x in right_sums:
        for left_group in left_sums[x]:
            for right_group in right_sums[S - x]:
                answers.append(sorted(left_group + right_group))

# 出力の昇順にソート
answers.sort()

# 結果を出力
for ans in answers:
    print(*ans)
0