#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);
int func(int i, int j) {
if (i < 0 or j < 0) {
return 0;
}
if (dp[i][j] != -1) {
return dp[i][j];
}
int answer = 0;
for (auto [child, weight] : graph[i]) {
for (int wt = j - weight; wt >= 0; wt--) {
answer += func(child, wt);
}
}
return dp[i][j] = answer;
}
void solve(bool testCases = true) {
int T = 1;
if (testCases) cin >> T;
while (T--) {
cin >> n >> m >> h;
memset(dp, -1, sizeof(dp));
for (int i = 0; i < m; i++) {
dp[0][0] = 0;
}
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 = 0; i < m; i++) {
cout << min(func(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;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
16732 KB |
Output is correct |
2 |
Correct |
3 ms |
16588 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
200 ms |
262144 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
16732 KB |
Output is correct |
2 |
Correct |
3 ms |
16588 KB |
Output is correct |
3 |
Runtime error |
200 ms |
262144 KB |
Execution killed with signal 9 |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
16732 KB |
Output is correct |
2 |
Correct |
3 ms |
16588 KB |
Output is correct |
3 |
Runtime error |
200 ms |
262144 KB |
Execution killed with signal 9 |
4 |
Halted |
0 ms |
0 KB |
- |