結果

問題 No.1238 選抜クラス
ユーザー tktk_snsn
提出日時 2021-01-13 01:33:36
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 59 ms / 2,000 ms
コード長 617 bytes
コンパイル時間 156 ms
コンパイル使用メモリ 82,436 KB
実行使用メモリ 75,784 KB
最終ジャッジ日時 2024-11-21 15:04:57
合計ジャッジ時間 3,530 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 36
権限があれば一括ダウンロードができます

ソースコード

diff # 

mod = 10 ** 9 + 7
U = 10000

N, K = map(int, input().split())
A = list(map(int, input().split()))


pos = []
neg = []
for a in A:
    a -= K
    if a >= 0:
        pos.append(a)
    else:
        neg.append(-a)


def calc_DP(X):
    dp = [0] * (U + 1)
    dp[0] = 1
    for p in X:
        for i in reversed(range(p, U + 1)):
            dp[i] += dp[i - p]
            dp[i] %= mod
    dp[0] -= 1
    return dp


pos = calc_DP(pos)
neg = calc_DP(neg)
for i in range(1, U + 1):
    neg[i] += neg[i - 1]
    neg[i] %= mod

ans = sum(pos) % mod
for i, v in enumerate(pos):
    ans += v * neg[i]
    ans %= mod
print(ans)
0