結果
問題 |
No.1111 コード進行
|
ユーザー |
|
提出日時 | 2020-07-10 22:39:28 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,017 ms / 2,000 ms |
コード長 | 903 bytes |
コンパイル時間 | 227 ms |
コンパイル使用メモリ | 81,932 KB |
実行使用メモリ | 196,240 KB |
最終ジャッジ日時 | 2024-10-11 10:01:06 |
合計ジャッジ時間 | 9,632 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 48 |
ソースコード
MOD=10**9+7 n=300 N,M,K=map(int,input().split()) P=[0]*M Q=[0]*M C=[0]*M for i in range(M): P[i],Q[i],C[i]=map(int,input().split()) P[i]-=1 Q[i]-=1 dp0=[[0]*(K+1) for i in range(n)] dp1=[[0]*(K+1) for i in range(n)] for i in range(n): dp0[i][0]=1 for t in range(N-1): for i in range(M): for num in range(K+1): nnum=num+C[i] if nnum>K: continue if t%2==0: dp1[Q[i]][nnum]+=dp0[P[i]][num] if dp1[Q[i]][num]>=MOD: dp1[Q[i]][nnum]-=MOD else: dp0[Q[i]][nnum]+=dp1[P[i]][num] if dp0[Q[i]][nnum]>=MOD: dp0[Q[i]][nnum]-=MOD if t%2==0: dp0=[[0]*(K+1) for i in range(n)] else: dp1=[[0]*(K+1) for i in range(n)] ans=0 for i in range(n): ans=(ans+dp0[i][K]+dp1[i][K])%MOD print(ans)