제출 #947493

#제출 시각아이디문제언어결과실행 시간메모리
947493devkudawlaJourney (NOI18_journey)C++17
20 / 100
3 ms16732 KiB
#include <bits/stdc++.h> using namespace std; int n, m, h; const int N = 10010, M = 410; int dp[N + 1][M + 1]; vector<vector<pair<int, int>>> graph(N + 1); void solve(bool testCases = true) { int T = 1; if (testCases) cin >> T; while (T--) { cin >> n >> m >> h; memset(dp, 0, sizeof(dp)); dp[0][0] = 1; for (int i = 0; i < n - 1; i++) { for (int j = 0; j < h; j++) { int a, b; cin >> a >> b; if (i > a) { continue; } graph[a].push_back({i, b}); } } for (int i = 1; i < n; i++) { for (int j = 0; j < m; j++) { for (auto [child, weight] : graph[i]) { for (int wt = j - weight; wt >= 0; wt--) { dp[i][j] += dp[child][wt]; } } } } for (int i = 0; i < m; i++) { cout << min(dp[n - 1][i], 500000001); cout << " "; } cout << "\n"; } } int32_t main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); solve(false); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...