Submission #548826

#TimeUsernameProblemLanguageResultExecution timeMemory
548826jack715Journey (NOI18_journey)C++14
100 / 100
168 ms10184 KiB
#include <bits/stdc++.h> #define ll long long #define pb push_back #define pp pop_back #define mp make_pair #define bb back #define ff first #define ss second #define int long long using namespace std; signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, m, h; cin >> n >> m >> h; vector<vector<pair<int, int> > > path(n, vector<pair<int, int> >(h)); for (int i = 0; i < n-1; i++) for (int j = 0; j < h; j++) cin >> path[i][j].ff >> path[i][j].ss; vector<vector<int> > reach(n, vector<int>(m, 0)); reach[0][0] = 1; for (int i = 0; i < n-1; i++) { vector<int> sum(m+1); sum[0] = reach[i][0]; for (int j = 1; j < m; j++) sum[j] = sum[j-1] + reach[i][j]; for (int p = 0; p < h; p++) { if (path[i][p].ff <= i) continue; for (int j = path[i][p].ss; j < m; j++) { reach[path[i][p].ff][j] = min((long long)500000001, sum[j-path[i][p].ss]+reach[path[i][p].ff][j]); } } } for (int i = 0; i < m; i++) cout << reach[n-1][i] << ' '; cout << '\n'; 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...