結果

問題 No.15 カタログショッピング
ユーザー zimphazimpha
提出日時 2017-12-07 22:03:47
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 92 ms / 5,000 ms
コード長 652 bytes
コンパイル時間 212 ms
コンパイル使用メモリ 82,632 KB
実行使用メモリ 82,784 KB
最終ジャッジ日時 2024-11-29 05:19:22
合計ジャッジ時間 1,403 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 34 ms
52,336 KB
testcase_01 AC 35 ms
52,532 KB
testcase_02 AC 33 ms
52,504 KB
testcase_03 AC 39 ms
60,556 KB
testcase_04 AC 35 ms
53,140 KB
testcase_05 AC 74 ms
77,076 KB
testcase_06 AC 78 ms
77,980 KB
testcase_07 AC 86 ms
82,784 KB
testcase_08 AC 92 ms
82,668 KB
testcase_09 AC 86 ms
82,740 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

def convert(mask, n):
  r = []
  for i in range(n):
    if mask >> i & 1:
      r.append(i + 1)
  return r

n, s = list(map(int, input().split()))
p = [int(input()) for i in range(n)]

x, y = n // 2, n - n // 2
cache = dict()
for mask in range(1 << x):
  r = 0
  for i in range(x):
    if mask >> i & 1:
      r += p[i]
  if r in cache:
    cache[r].append(mask)
  else:
    cache[r] = [mask]

ret = []
for mask in range(1 << y):
  r = s
  for i in range(y):
    if mask >> i & 1:
      r -= p[i + x]
  if r in cache:
    for e in cache[r]:
      ret.append(e | (mask << x))
ret = [convert(mask, n) for mask in ret]
ret.sort()
for e in ret:
  print(*e)
0