結果
問題 |
No.1111 コード進行
|
ユーザー |
![]() |
提出日時 | 2020-07-14 22:12:41 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,124 ms / 2,000 ms |
コード長 | 1,241 bytes |
コンパイル時間 | 1,908 ms |
コンパイル使用メモリ | 184,116 KB |
実行使用メモリ | 116,352 KB |
最終ジャッジ日時 | 2024-11-18 22:51:52 |
合計ジャッジ時間 | 15,379 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 48 |
ソースコード
#include <bits/stdc++.h> #define rep(i, n) for (int i = 0; i < (int)(n); i++) using namespace std; typedef long long ll; typedef vector<int> vi; typedef vector<long long> vl; int main() { int N, M, K; cin >> N >> M >> K; vi P(M), Q(M), C(M); rep(i, M) { cin >> P[i] >> Q[i] >> C[i]; P[i]--; Q[i]--; } const int MOD = 1000000007; const int MAX = 305; map<int, vector<pair<int, int>>> G; rep(i, M) { G[P[i]].push_back(make_pair(Q[i], C[i])); } vector<vector<vector<int>>> dp(N + 1, vector<vector<int>>(MAX, vector<int>(MAX))); rep(i, M) { dp[0][Q[i]][C[i]]++; } for (int i = 0; i < N; i++) { for (int j = 0; j < MAX; j++) { for (int k = 0; k < MAX; k++) { for (int l = 0; l < G[j].size(); l++) { int nj = G[j][l].first; int ncost = k + G[j][l].second; if (ncost > K) continue; dp[i + 1][nj][ncost] += dp[i][j][k]; dp[i + 1][nj][ncost] %= MOD; } } } } int cnt = 0; rep(i, MAX) { cnt += dp[N - 2][i][K]; cnt %= MOD; } cout << cnt << endl; }