結果
問題 | No.15 カタログショッピング |
ユーザー | nsd_fb |
提出日時 | 2015-02-20 11:16:47 |
言語 | Python2 (2.7.18) |
結果 |
AC
|
実行時間 | 461 ms / 5,000 ms |
コード長 | 834 bytes |
コンパイル時間 | 390 ms |
コンパイル使用メモリ | 6,616 KB |
実行使用メモリ | 63,292 KB |
最終ジャッジ日時 | 2023-09-06 02:28:22 |
合計ジャッジ時間 | 3,485 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 11 ms
5,952 KB |
testcase_01 | AC | 11 ms
5,900 KB |
testcase_02 | AC | 11 ms
6,064 KB |
testcase_03 | AC | 12 ms
6,140 KB |
testcase_04 | AC | 11 ms
5,900 KB |
testcase_05 | AC | 457 ms
63,108 KB |
testcase_06 | AC | 456 ms
63,252 KB |
testcase_07 | AC | 455 ms
63,228 KB |
testcase_08 | AC | 461 ms
63,292 KB |
testcase_09 | AC | 445 ms
63,172 KB |
ソースコード
def dfs(index, money, goods, dic, end): global N, S, P if goods: dic.setdefault(money, []).append(list(goods)) if index == end: return goods.append(index + 1) dfs(index + 1, money + P[index], goods, dic, end) goods.pop() dfs(index + 1, money, goods, dic, end) N, S = map(int, raw_input().split()) P = [int(raw_input()) for i in xrange(N)] first = {0:[[]]} second = {0:[[]]} dfs(0, 0, [], first, N / 2) dfs(N / 2, 0, [], second, N) ans = [] for money, l in first.iteritems(): if not S - money in second: continue for first_goods in l: for second_goods in second[S - money]: goods = first_goods + second_goods if not goods in ans: ans.append(goods) ans.sort() for goods in ans: print ' '.join(map(str, goods))