結果

問題 No.15 カタログショッピング
ユーザー zimphazimpha
提出日時 2017-12-07 22:03:47
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 136 ms / 5,000 ms
コード長 652 bytes
コンパイル時間 464 ms
コンパイル使用メモリ 86,984 KB
実行使用メモリ 83,656 KB
最終ジャッジ日時 2023-08-19 12:27:14
合計ジャッジ時間 2,355 ms
ジャッジサーバーID
（参考情報） 		judge10 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 78 ms
71,336 KB
testcase_01 AC 78 ms
71,216 KB
testcase_02 AC 77 ms
71,252 KB
testcase_03 AC 83 ms
76,252 KB
testcase_04 AC 78 ms
71,232 KB
testcase_05 AC 128 ms
83,376 KB
testcase_06 AC 132 ms
83,656 KB
testcase_07 AC 132 ms
83,204 KB
testcase_08 AC 136 ms
83,588 KB
testcase_09 AC 131 ms
83,444 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