#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define mp make_pair
#define pb push_back
#define bas(x) #x << ": " << x << " "
#define prarr(x, n) cout << #x << ": "; for (int qsd = 0; qsd < n; qsd++) cout << x[qsd] << " "; cout << endl;
#define prarrv(x) cout << #x << ": "; for (int qsd = 0; qsd < (int)x.size(); qsd++) cout << x[qsd] << " "; cout << endl;
#define ppair(x) "(" << x.first << ", " << x.second << ")"
#define inside sl<=l&&r<=sr
#define outside sr<l||r<sl
typedef long long ll;
ll inf = 500000001;
int n, m, h;
vector<pair<ll, ll> > ways[10004];
ll dp[10004][404];
ll pre[10004][404];
int main(){
//freopen("in", "r", stdin);
//freopen("out", "w", stdout);
cin >> n >> m >> h;
for (int i = 0; i < n-1; i++){
for (int j = 0; j < h; j++){
ll a, b;
cin >> a >> b;
ways[i].pb(mp(a, b));
}
}
for (int i = 0; i < m; i++) dp[n-1][i] = 1;
for (int i = 0; i < m; i++) pre[n-1][i] = i+1;
for (int i = n-2; i >= 0; i--){
for (int d = 0; d < m; d++){
for (int j = 0; j < h; j++){
if (ways[i][j].first <= i) continue;
if (d-ways[i][j].second < 0) continue;
dp[i][d] += pre[ways[i][j].first][d-ways[i][j].second];
dp[i][d] = min(dp[i][d], inf);
}
}
ll sum = 0;
for (int it = 0; it < m; it++){
sum += dp[i][it];
sum = min(inf, sum);
pre[i][it] = sum;
}
}
/*for (int i = 0; i < n; i++){
for (int j = 0; j < m; j++){
cout << dp[i][j] << " ";
}
cout << endl;
}
cout << endl;
*/
vector<ll> ans(m, 0);
for (int j = 0; j < h; j++){
for (int d = 0; d < m; d++){
if (d-ways[0][j].second >= 0) ans[d] += dp[ways[0][j].first][d-ways[0][j].second];
ans[d] = min(ans[d], inf);
}
}
for (int i = 0; i < ans.size(); i++) cout << ans[i] << " "; cout << endl;
}
Compilation message
journey.cpp: In function 'int main()':
journey.cpp:72:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < ans.size(); i++) cout << ans[i] << " "; cout << endl;
~~^~~~~~~~~~~~
journey.cpp:72:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
for (int i = 0; i < ans.size(); i++) cout << ans[i] << " "; cout << endl;
^~~
journey.cpp:72:62: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
for (int i = 0; i < ans.size(); i++) cout << ans[i] << " "; cout << endl;
^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
632 KB |
Output is correct |
| 2 |
Correct |
2 ms |
632 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
760 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
632 KB |
Output is correct |
| 2 |
Correct |
2 ms |
632 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
760 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
632 KB |
Output is correct |
| 2 |
Correct |
2 ms |
632 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
760 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
