結果
問題 |
No.1111 コード進行
|
ユーザー |
|
提出日時 | 2020-07-10 22:42:46 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 309 ms / 2,000 ms |
コード長 | 1,088 bytes |
コンパイル時間 | 4,604 ms |
コンパイル使用メモリ | 241,248 KB |
実行使用メモリ | 225,280 KB |
最終ジャッジ日時 | 2024-10-11 10:04:56 |
合計ジャッジ時間 | 16,566 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
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; using ll = long long ; using P = pair<int,int> ; using pll = pair<long long,long long>; constexpr int INF = 1e9; constexpr long long LINF = 1e17; constexpr int MOD = 1000000007; constexpr double PI = 3.14159265358979323846; int n,m,k; vector<vector<P>> graph(305,vector<P>()); ll dp[305][305][305] = {-1}; ll dfs(int i,int cnt,int cost){ if(dp[i][cnt][cost]>=0) return dp[i][cnt][cost]; if(cnt==0){ if(cost==0) return 1; else return 0; } ll res = 0; rep(j,graph[i].size()){ if(cost-graph[i][j].first<0) continue; ll p = dfs(graph[i][j].second,cnt-1,cost-graph[i][j].first); res = (res + p)%MOD; } return dp[i][cnt][cost] = res; } int main(){ rep(i,305)rep(j,305)rep(k,305) dp[i][j][k] = -1; cin >> n >> m >> k; rep(i,m){ int p,q,c; cin >> p >> q >> c; graph[p].push_back(P(c,q)); } for(int i=1;i<305;i++) graph[0].push_back(P(0,i)); cout << dfs(0,n,k) << endl; return 0; }