# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1020343 | daffuwu | Journey (NOI18_journey) | C++14 | 0 ms | 0 KiB |
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;
#define nyahalo ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define otsumiko exit(0);
#define mikodanye priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > >
#define mikochi priority_queue<int, vector<int>, greater<int> >
int n, m, h, dp[10003][403], u, v, mx = 500000001, k, ps[1003][403];
vector<pair<int, int> > al[10003];
int main() {
nyahalo
int i, j, ii;
cin >> n >> m >> h;
for (i=0; i<=n-2; i++) {
for (j=1; j<=h; j++) {
cin >> u >> k;
if (u>i) {
al[u].push_back(make_pair(i, k));
}
}
}
for (i=0; i<=m-1; i++) {
if (i == 0) {
dp[0][i] = 1;
ps[0][i] = dp[0][i];
} else {
dp[0][i] = 0;
ps[0][i] = ps[0][i-1]+dp[0][i];
ps[0][i] = min(ps[0][i], mx);
}
}
for (i=1; i<=n-1; i++) {
for (j=0; j<=m-1; j++) {
dp[i][j] = 0;
for (ii=0; ii<al[i].size(); ii++) {
u = al[i][ii].first;
k = al[i][ii].second;
if (j>=k) {
dp[i][j] += ps[u][j-k];
dp[i][j] = min(dp[i][j], mx);
}
}
if (j == 0) {
ps[i][j] = dp[i][j];
} else {
ps[i][j] = ps[i][j-1]+dp[i][j];
ps[i][j] = min(ps[i][j], mx);
}
}
}
for (i=0; i<=m-1; i++) {
cout << dp[n-1][i];
if (i == m-1) {
cout << "\n";
} else {
cout << " ";
}
}
otsumiko