結果
問題 | No.15 カタログショッピング |
ユーザー |
|
提出日時 | 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 |
ソースコード
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)