結果
問題 |
No.1011 Infinite Stairs
|
ユーザー |
![]() |
提出日時 | 2020-03-20 23:51:00 |
言語 | D (dmd 2.109.1) |
結果 |
AC
|
実行時間 | 268 ms / 2,000 ms |
コード長 | 1,191 bytes |
コンパイル時間 | 3,617 ms |
コンパイル使用メモリ | 175,928 KB |
実行使用メモリ | 109,116 KB |
最終ジャッジ日時 | 2024-06-22 05:46:18 |
合計ジャッジ時間 | 4,473 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 24 |
ソースコード
import std; int tle(int n, int d, int k) { const MOD = 10^^9 + 7; auto dp = new int[][](n + 1, k + 1); dp[0][0] = 1; for (int i = 1; i <= n; i++) { for (int j = 0; j < k; j++) { for (int m = 1; m <= d; m++) { if (j + m > k) break; dp[i][j+m] = (dp[i][j+m] + dp[i-1][j]) % MOD; } } } return dp[n][k]; } int calc(int n, int d, int k) { const MOD = 10^^9 + 7; auto dp = new int[][](n + 1, k + 1); dp[0][0] = 1; auto acc = new int[k + 1]; for (int i = 1; i <= n; i++) { for (int j = 1; j <= k; j++) { acc[j] = (acc[j-1] + dp[i-1][j-1]) % MOD; } for (int j = 1; j <= k; j++) { dp[i][j] += acc[j] - acc[max(j - d, 0)]; dp[i][j] %= MOD; } } return (dp[n][k] + MOD) % MOD; } void main() { int n, d, k; scan(n, d, k); writeln(calc(n, d, k)); } void scan(T...)(ref T a) { string[] ss = readln.split; foreach (i, t; T) a[i] = ss[i].to!t; } T read(T)() { return readln.chomp.to!T; } T[] reads(T)() { return readln.split.to!(T[]); } alias readint = read!int; alias readints = reads!int;