結果
問題 |
No.1111 コード進行
|
ユーザー |
![]() |
提出日時 | 2022-05-20 10:35:32 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 462 ms / 2,000 ms |
コード長 | 779 bytes |
コンパイル時間 | 291 ms |
コンパイル使用メモリ | 82,292 KB |
実行使用メモリ | 295,640 KB |
最終ジャッジ日時 | 2024-09-19 17:57:41 |
合計ジャッジ時間 | 7,241 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 48 |
ソースコード
N, M, K = map(int, input().split()) code = [list() for _ in range(300)] for i in range(M): p, q, c = map(int, input().split()) code[p-1].append([q-1, c]) mod = 10**9+7 dp = [[[0]*(K+1) for _ in range(300)] for _ in range(N)] for i in range(N-1): if i == 0: for j in range(300): for nex, c in code[j]: if c <= K: dp[i+1][nex][c] += 1 else: for j in range(300): for k in range(K+1): if dp[i][j][k] > 0: for nex, c in code[j]: if k+c <= K: dp[i+1][nex][k+c] += dp[i][j][k] dp[i+1][nex][k+c] %= mod sm = 0 for i in range(300): sm += dp[-1][i][-1] sm %= mod print(sm)