結果
問題 | No.15 カタログショッピング |
ユーザー |
|
提出日時 | 2021-02-06 08:54:30 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 113 ms / 5,000 ms |
コード長 | 913 bytes |
コンパイル時間 | 151 ms |
コンパイル使用メモリ | 82,116 KB |
実行使用メモリ | 89,896 KB |
最終ジャッジ日時 | 2024-07-02 16:31:31 |
合計ジャッジ時間 | 1,570 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 10 |
ソースコード
from collections import defaultdict N, S = map(int, input().split()) P = [int(input()) for _ in range(N)] def full_search(X): L = len(X) table = [0] * (1 << L) for b in range(1 << L): for i in range(L): if b & (1 << i): table[b] = table[b ^ (1 << i)] + X[i] return table lsum, rsum = full_search(P[:N // 2]), full_search(P[N // 2:]) r_dict = defaultdict(list) for b, x in enumerate(rsum): r_dict[x].append(b) r_dict = dict(r_dict) def decode(b, l): for i in range(l): if b & (1 << i): yield i + 1 ans = [] for bl, x in enumerate(lsum): if S - x in r_dict: for br in r_dict[S - x]: tmp = list(decode(bl, N // 2)) for x in decode(br, N - N // 2): tmp.append(x + N // 2) tmp = tuple(sorted(tmp)) ans.append(tmp) ans.sort() for t in ans: print(*t)