結果
問題 | No.15 カタログショッピング |
ユーザー |
|
提出日時 | 2023-06-08 09:06:59 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 238 ms / 5,000 ms |
コード長 | 1,307 bytes |
コンパイル時間 | 293 ms |
コンパイル使用メモリ | 82,176 KB |
実行使用メモリ | 120,732 KB |
最終ジャッジ日時 | 2024-12-30 15:52:11 |
合計ジャッジ時間 | 2,509 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 10 |
ソースコード
from collections import * from itertools import * from functools import * from heapq import * import sys,math input = sys.stdin.readline N,S = map(int,input().split()) P = [int(input()) for i in range(N)] if N==1: print(1) exit() n = N//2 m = N-n P0 = P[:n] P1 = P[n:] S0 = defaultdict(lambda:[]) S1 = defaultdict(lambda:[]) Z0 = [] Z1 = [] def cle(a,D): y = len(D)-1 x = 0 if D[x]>a: return 0 if D[y]<=a: return y+1 while y-x>1: mid = (y+x)//2 if D[mid]<=a: x = mid else: y = mid return y for i in range(1<<n): tmp = 0 for j in range(n): if (i>>j)&1: tmp += P0[j] Z0.append(int(tmp)) S0[tmp].append(i) for i in range(1<<m): tmp = 0 for j in range(m): if (i>>j)&1: tmp += P1[j] Z1.append(int(tmp)) S1[tmp].append(i) Z0 = list(set(Z0)) Z1 = list(set(Z1)) Z0.sort() Z1.sort() ans = [] for z0 in Z0: t = cle(S-z0,Z1) if t==0: continue for tx in S0[z0]: for ty in S1[S-z0]: ans.append(tx + (ty<<n)) Z = [] for a in ans: tmp = [] for i in range(N): if (a>>i)&1: tmp.append(i+1) Z.append(tuple(tmp)) Z.sort() for z in Z: print(*z)