結果
問題 | No.15 カタログショッピング |
ユーザー |
|
提出日時 | 2022-02-07 14:18:26 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,607 ms / 5,000 ms |
コード長 | 1,015 bytes |
コンパイル時間 | 340 ms |
コンパイル使用メモリ | 82,432 KB |
実行使用メモリ | 412,296 KB |
最終ジャッジ日時 | 2024-06-12 20:53:42 |
合計ジャッジ時間 | 9,083 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 10 |
ソースコード
from itertools import product from bisect import bisect_right n, s = map(int, input().split()) p = [int(input()) for _ in range(n)] cnt = min(20, n) item1 = [] bisect_item1 = [] for i in product([0, 1], repeat=cnt): money, item = 0, [] for j in range(cnt): if i[j] == 1: money += p[j] item.append(j + 1) item1.append([money, item]) bisect_item1.append(money) cnt = max(0, n - 20) item2 = [] bisect_item2 = [] for i in product([0, 1], repeat=cnt): money, item = 0, [] for j in range(cnt): if i[j] == 1: money += p[j + 20] item.append(j + 21) item2.append([money, item]) bisect_item2.append(money) item2.sort(key=lambda x: x[0]) bisect_item2.sort() ans = [] for money, item in item1: if money > s: continue p = bisect_right(bisect_item2, s - money) if money + bisect_item2[p - 1] == s: a = item b = item2[p - 1][1] ans.append(sorted(a + b)) ans.sort() for i in ans: print(*i)