結果
問題 |
No.1111 コード進行
|
ユーザー |
![]() |
提出日時 | 2019-10-13 18:59:05 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 320 ms / 2,000 ms |
コード長 | 1,463 bytes |
コンパイル時間 | 2,144 ms |
コンパイル使用メモリ | 183,808 KB |
実行使用メモリ | 217,856 KB |
最終ジャッジ日時 | 2024-10-01 15:25:56 |
合計ジャッジ時間 | 4,988 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 48 |
ソースコード
#include <bits/stdc++.h> using namespace std; int main() { const long mod = 1000000007; int n, m, k; cin >> n >> m >> k; assert(2 <= n && n <= 300); assert(1 <= m && m <= 300); assert(0 <= k && k <= 300); vector<int> p(m), q(m), c(m); vector<pair<int, int>> check; for (int i = 0; i < m; i++) { cin >> p.at(i) >> q.at(i) >> c.at(i); assert(1 <= p.at(i) && p.at(i) <= 300); assert(1 <= q.at(i) && q.at(i) <= 300); assert(p.at(i) != q.at(i)); assert(0 <= c.at(i) && c.at(i) <= 300); check.emplace_back(p.at(i), q.at(i)); } sort(check.begin(), check.end()); for (int i = 0; i < m - 1; i++) { assert(check.at(i) != check.at(i + 1)); } for (int i = 0; i < m; i++) { p.at(i)--; q.at(i)--; } vector<vector<vector<long>>> dp(n - 1, vector<vector<long>>(300, vector<long>(k + 1))); for (int i = 0; i < m; i++) { if (c.at(i) <= k) dp.at(0).at(q.at(i)).at(c.at(i))++; } for (int i = 1; i < n - 1; i++) { for (int j = 0; j < m; j++) { for (int comp = c.at(j); comp <= k; comp++) { dp.at(i).at(q.at(j)).at(comp) += dp.at(i - 1).at(p.at(j)).at(comp - c.at(j)); dp.at(i).at(q.at(j)).at(comp) %= mod; } } } long ans = 0; for (int i = 0; i < 300; i++) { ans += dp.at(n - 2).at(i).at(k); ans %= mod; } cout << ans << endl; }