# IOI '99 P1 - Little Shop of Flowers

Jun 7th, 2022
1,446
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include <iostream>
2. #include <vector>
3.
4. using namespace std;
5.
6. const int INF = 1e9;
7.
8. int main() {
9.     int f, v;
10.     cin >> f >> v;
11.     vector<vector<int>> value(f, vector<int>(v));
12.     for (vector<int> &row : value) {
13.         for (int &x : row) cin >> x;
14.     }
15.     vector<vector<int>> dp(1+f, vector<int>(1+v)), lastPos(1+f, vector<int>(1+v, -1));
16.     /* dp[i][j] is max value of first i bunches
17.         of flowers only using the first j vases */
18.     for (int i = 1; i <= f; ++i) {
19.         for (int j = 0; j <= v; ++j) {
20.             if (j < i) dp[i][j] = -INF;
21.             else if (dp[i][j-1] > dp[i-1][j-1] + value[i-1][j-1]) {
22.                 dp[i][j] = dp[i][j-1], lastPos[i][j] = lastPos[i][j-1];
23.             } else {
24.                 dp[i][j] = dp[i-1][j-1] + value[i-1][j-1], lastPos[i][j] = j;
25.             }
26.         }
27.     }
28.     cout << dp[f][v] << endl;
29.     vector<int> a;
30.     for (int i = f, j = v; i; j = lastPos[i--][j]-1) a.push_back(lastPos[i][j]);
31.     for (int i = f-1; i >= 0; --i) cout << a[i] << ' ';
32.     cout << endl;
33.     return 0;
34. }
35.