This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 10005;
const int MAX_M = 405;
const int MOD = 500000001;
int dp[MAX_N][MAX_M];
vector <pair <int, int>> graph[MAX_N];
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int N, M, H;
cin >> N >> M >> H;
for(int i = 0; i < N - 1; i++) {
for(int h = 0; h < H; h++) {
int j, k;
cin >> j >> k;
graph[i].emplace_back(j, k);
}
}
dp[0][0] = 1;
for(int i = 0; i < N - 1; i++) {
for(int m = 1; m < M; m++) {
dp[i][m] += dp[i][m - 1];
dp[i][m] = min(dp[i][m], MOD);
}
for(auto [j, k] : graph[i]) {
for(int m = 0; m + k < M; m++) {
dp[j][m + k] += dp[i][m];
dp[j][m + k] = min(dp[j][m + k], MOD);
}
}
}
for(int m = 0; m < M; m++) {
cout << dp[N - 1][m] << ' ';
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |