結果
問題 | No.1238 選抜クラス |
ユーザー |
![]() |
提出日時 | 2020-09-25 21:49:53 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 55 ms / 2,000 ms |
コード長 | 761 bytes |
コンパイル時間 | 528 ms |
コンパイル使用メモリ | 82,116 KB |
実行使用メモリ | 62,208 KB |
最終ジャッジ日時 | 2024-06-28 06:23:29 |
合計ジャッジ時間 | 3,296 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 36 |
ソースコード
import sys input = sys.stdin.readline N, K = map(int, input().split()) a = list(map(int, input().split())) mod = 10 ** 9 + 7 a.sort() for i in range(N): a[i] -= K mn = [] zr = 0 pl = [] for x in a: if x < 0: mn.append(-x) elif x == 0: zr += 1 else: pl.append(x) ln = N * 100 dpmn = [0] * (ln + 1) dpmn[0] = 1 dppl = [0] * (ln + 1) dppl[0] = 1 for x in mn: for i in range(ln, -1, -1): if dpmn[i]: dpmn[i + x] += dpmn[i] dpmn[i + x] %= mod for x in pl: for i in range(ln, -1, -1): if dppl[i]: dppl[i + x] += dppl[i] dppl[i + x] %= mod for i in range(ln, 0, -1): dppl[i - 1] += dppl[i] dppl[i - 1] %= mod res = 0 for i in range(ln + 1): res += dppl[i] * dpmn[i] res %= mod print((res * pow(2, zr, mod) - 1) % mod)