結果

問題 No.616 へんなソート
ユーザー ああいい
提出日時 2022-03-30 19:34:50
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 438 ms / 2,000 ms
コード長 445 bytes
コンパイル時間 241 ms
コンパイル使用メモリ 82,200 KB
実行使用メモリ 250,240 KB
最終ジャッジ日時 2024-11-15 10:17:18
合計ジャッジ時間 3,710 ms
ジャッジサーバーID
(参考情報)
judge2 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 27
権限があれば一括ダウンロードができます

ソースコード

diff #

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

a.sort()
P = 10 ** 9 + 7
dp = [0] * (K+1)
dp[0] = 1
for i in range(N):
    nx = [0] * (K + 1)
    S = [0] * (K + 2)
    for j in range(K+1):
        S[j+1] = (S[j] + dp[j]) % P
    for j in range(K+1):
        tmp = S[j+1] - S[max(0,j-i)]
        nx[j] += tmp

    
    for u in range(K+1):
        nx[u] %= P
    dp = nx
ans = 0
for i in dp:
    ans = (ans + i) % P
print(ans)
0