結果
問題 |
No.1111 コード進行
|
ユーザー |
![]() |
提出日時 | 2025-03-20 21:08:06 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 293 ms / 2,000 ms |
コード長 | 1,206 bytes |
コンパイル時間 | 264 ms |
コンパイル使用メモリ | 82,380 KB |
実行使用メモリ | 92,088 KB |
最終ジャッジ日時 | 2025-03-20 21:08:30 |
合計ジャッジ時間 | 6,311 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 48 |
ソースコード
MOD = 10**9 + 7 def main(): import sys input = sys.stdin.read().split() idx = 0 N = int(input[idx]); idx +=1 M = int(input[idx]); idx +=1 K = int(input[idx]); idx +=1 edges = [[] for _ in range(301)] for _ in range(M): p = int(input[idx]); idx +=1 q = int(input[idx]); idx +=1 c = int(input[idx]); idx +=1 edges[p].append( (q, c) ) # DP initialization: prev[j][k] = count for position 1, j with cost k (which is 0) prev = [[0]*(K+1) for _ in range(301)] for j in range(1, 301): prev[j][0] = 1 for _ in range(N-1): # N-1 transitions needed curr = [[0]*(K+1) for _ in range(301)] for j in range(1, 301): for k in range(K+1): if prev[j][k] == 0: continue for (q, c) in edges[j]: new_k = k + c if new_k > K: continue curr[q][new_k] = (curr[q][new_k] + prev[j][k]) % MOD prev = curr total = 0 for j in range(1, 301): total = (total + prev[j][K]) % MOD print(total % MOD) if __name__ == '__main__': main()