結果

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

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 40 ms
51,968 KB
testcase_01 AC 38 ms
51,968 KB
testcase_02 AC 39 ms
52,224 KB
testcase_03 AC 46 ms
60,160 KB
testcase_04 AC 39 ms
52,096 KB
testcase_05 AC 83 ms
77,440 KB
testcase_06 AC 93 ms
77,952 KB
testcase_07 AC 101 ms
82,560 KB
testcase_08 AC 98 ms
82,560 KB
testcase_09 AC 97 ms
82,432 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