Submission #828897

#TimeUsernameProblemLanguageResultExecution timeMemory
828897NK_Journey (NOI18_journey)C++17
20 / 100
1 ms324 KiB
// Success consists of going from failure to failure without loss of enthusiasm #include <bits/stdc++.h> using namespace std; #define nl '\n' #define pb push_back #define mp make_pair #define f first #define s second #define sz(x) int(x.size()) template<class T> using V = vector<T>; using vi = V<int>; using ll = long long; using pi = pair<int, int>; using vpi = V<pi>; using vl = V<ll>; using db = double; const int INF = 5e8 + 1; int main() { cin.tie(0)->sync_with_stdio(0); int N, M, H; cin >> N >> M >> H; V<vpi> nxt(N); for(int i = 0; i < N - 1; i++) { for(int t = 0; t < H; t++) { int u, x; cin >> u >> x; if (u < i) continue; nxt[i].pb(mp(u, x)); } } V<vi> dp(N, vi(M, 0)); dp[0][0] = 1; for(int u = 0; u < N; u++) { for(auto& e : nxt[u]) { auto [v, d] = e; int ways = 0; for(int x = 0; x < M - d; x++) { ways = min(INF, ways + dp[u][x]); dp[v][x + d] = min(INF, dp[v][x + d] + ways); } } } for(int x = 0; x < M; x++) cout << dp[N-1][x] << " "; cout << nl; exit(0-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...