結果
問題 | No.15 カタログショッピング |
ユーザー |
👑 |
提出日時 | 2022-07-06 07:41:59 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 136 ms / 5,000 ms |
コード長 | 776 bytes |
コンパイル時間 | 297 ms |
コンパイル使用メモリ | 82,264 KB |
実行使用メモリ | 100,308 KB |
最終ジャッジ日時 | 2024-12-18 02:00:12 |
合計ジャッジ時間 | 1,696 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 10 |
ソースコード
n, s = map(int, input().split()) P = [int(input()) for _ in range(n)] bef = P[:n // 2] aft = P[n // 2:] B = {} A = {} lb = len(bef) for bit in range(1 << lb): lst = [] tot = 0 for i in range(lb): if bit >> i & 1: lst.append(i + 1) tot += bef[i] if tot not in B: B[tot] = [] B[tot].append(lst[:]) la = len(aft) for bit in range(1 << la): lst = [] tot = 0 for i in range(la): if bit >> i & 1: lst.append(i + lb + 1) tot += aft[i] if tot not in A: A[tot] = [] A[tot].append(lst[:]) ans = [] for k in B: if s - k in A: for l1 in B[k]: for l2 in A[s - k]: ans.append(l1 + l2) ans.sort() for row in ans: print(*row)