結果
問題 | No.15 カタログショッピング |
ユーザー | dango |
提出日時 | 2023-07-08 17:50:30 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 270 ms / 5,000 ms |
コード長 | 904 bytes |
コンパイル時間 | 887 ms |
コンパイル使用メモリ | 86,852 KB |
実行使用メモリ | 92,836 KB |
最終ジャッジ日時 | 2023-09-29 19:13:00 |
合計ジャッジ時間 | 2,940 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 73 ms
71,284 KB |
testcase_01 | AC | 73 ms
71,424 KB |
testcase_02 | AC | 72 ms
71,284 KB |
testcase_03 | AC | 83 ms
76,036 KB |
testcase_04 | AC | 71 ms
71,472 KB |
testcase_05 | AC | 259 ms
92,836 KB |
testcase_06 | AC | 270 ms
92,680 KB |
testcase_07 | AC | 262 ms
92,632 KB |
testcase_08 | AC | 265 ms
92,716 KB |
testcase_09 | AC | 266 ms
92,716 KB |
ソースコード
from itertools import combinations def main(): n, s = map(int, input().split()) pi = [] for _ in range(n): pi.append(int(input())) if n == 1: if pi[0] == s: print(1) else: print(-1) return m1 = n // 2 m2 = n - m1 hi = {} for i in range(1 << m2): u = sum(pi[j + m1] for j in range(m2) if (i >> j) & 1) if u not in hi: hi[u] = [] hi[u].append(i) ri = [] for i in range(1 << m1): u = sum(pi[j] for j in range(m1) if (i >> j) & 1) w = s - u if w < 0 or w not in hi: continue ri.extend([(x << m1) | i for x in hi[w]]) if not ri: print(-1) else: ri2 = [sorted([j + 1 for j in range(n) if (r >> j) & 1]) for r in ri] ri2.sort() for r in ri2: print(" ".join(map(str, r))) main()