結果
問題 | No.15 カタログショッピング |
ユーザー | Tawara |
提出日時 | 2016-07-29 01:25:39 |
言語 | Python2 (2.7.18) |
結果 |
AC
|
実行時間 | 445 ms / 5,000 ms |
コード長 | 519 bytes |
コンパイル時間 | 464 ms |
コンパイル使用メモリ | 6,612 KB |
実行使用メモリ | 38,020 KB |
最終ジャッジ日時 | 2023-08-06 15:14:05 |
合計ジャッジ時間 | 3,082 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge15 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 13 ms
6,304 KB |
testcase_01 | AC | 13 ms
6,364 KB |
testcase_02 | AC | 13 ms
6,236 KB |
testcase_03 | AC | 14 ms
6,392 KB |
testcase_04 | AC | 13 ms
6,280 KB |
testcase_05 | AC | 439 ms
38,020 KB |
testcase_06 | AC | 445 ms
37,840 KB |
testcase_07 | AC | 436 ms
37,960 KB |
testcase_08 | AC | 438 ms
37,916 KB |
testcase_09 | AC | 442 ms
37,888 KB |
ソースコード
from collections import defaultdict XR = xrange; N,S = map(int,raw_input().split()) P = [int(raw_input()) for i in XR(N)] def enum(n,ofs): L = defaultdict(list) dp = [0]*(1<<n) for i in XR(1<<n): L[dp[i]].append(i) for j in XR(n): if i & (1<<j): continue dp[i|(1<<j)] = dp[i] + P[j+ofs] return L H = N/2 L1,L2 = enum(H,0),enum(N-H,H) ans = [] for v,l in L1.iteritems(): ans.extend([i+1 for i in XR(N) if(1<<i)&(b1+(b2<<H))] for b1 in l for b2 in L2[S-v]) for a in sorted(ans): print " ".join(map(str,a))