結果
問題 |
No.1011 Infinite Stairs
|
ユーザー |
![]() |
提出日時 | 2020-10-13 15:06:39 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 657 ms / 2,000 ms |
コード長 | 636 bytes |
コンパイル時間 | 218 ms |
コンパイル使用メモリ | 82,352 KB |
実行使用メモリ | 273,124 KB |
最終ジャッジ日時 | 2024-07-17 12:13:59 |
合計ジャッジ時間 | 4,706 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 24 |
ソースコード
N,d,K=map(int, input().split()) if K==1 or N==1 or d==1: print(1) exit() mod=10**9+7 dp=[[0 for i in range(K+1)] for j in range(N+1)] dp[0][0]=1 f=0 for i in range(K+1): if i==0: dp[1][i]=0 elif i<min(d+1,K): f+=1 dp[1][i]=f else: dp[1][i]=f for i in range(1,N): for j in range(1,K+1): if j-d-1>0: dp[i+1][j]=dp[i][j-1]-dp[i][j-d-1]+dp[i+1][j-1] dp[i+1][j]%=mod else: dp[i+1][j]=dp[i][j-1]+dp[i+1][j-1] dp[i+1][j]%=mod if dp[i+1][j]<0: dp[i+1][j]=0 print((dp[-1][-1]-dp[-1][-2])%mod)