結果
問題 |
No.1111 コード進行
|
ユーザー |
![]() |
提出日時 | 2020-07-11 01:17:56 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 587 ms / 2,000 ms |
コード長 | 839 bytes |
コンパイル時間 | 161 ms |
コンパイル使用メモリ | 81,876 KB |
実行使用メモリ | 97,500 KB |
最終ジャッジ日時 | 2024-10-11 22:16:41 |
合計ジャッジ時間 | 6,189 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 48 |
ソースコード
import sys read = sys.stdin.buffer.read readline = sys.stdin.buffer.readline readlines = sys.stdin.buffer.readlines n,m,k = map(int,readline().split()) pqc = list(map(int,read().split())) mod = 10**9+7 links = [dict() for _ in range(300+1)] it = iter(pqc) for p,q,c in zip(it,it,it): links[p][q] = c dp = [0,0] dp[0] = [[0] * (k+1) for _ in range(300+1)] dp[1] = [[0] * (k+1) for _ in range(300+1)] for j in range(1,300+1): dp[0][j][0] = 1 for i in range(n-1): i %= 2 i_next = 1-i dp[i_next] = [[0] * (k+1) for _ in range(300+1)] for j in range(1,301): for key,val in links[j].items(): for l in range(k-val+1): dp[i_next][j][l+val] += dp[i][key][l] dp[i_next][j][l+val] %= mod ans = 0 for j in range(1,301): ans += dp[i_next][j][k] ans %= mod print(ans)