結果

問題 No.15 カタログショッピング
コンテスト
ユーザー zimpha
提出日時 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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 10
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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