Advertisement
erek1e

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!
C++ 1.06 KB | None | 0 0
  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.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement