IOI '99 P1 - Little Shop of Flowers

#include <iostream>
#include <vector>

using namespace std;

const int INF = 1e9;

int main() {
    int f, v;
    cin >> f >> v;
    vector<vector<int>> value(f, vector<int>(v));
    for (vector<int> &row : value) {
        for (int &x : row) cin >> x;
    }
    vector<vector<int>> dp(1+f, vector<int>(1+v)), lastPos(1+f, vector<int>(1+v, -1));
    /* dp[i][j] is max value of first i bunches
        of flowers only using the first j vases */
    for (int i = 1; i <= f; ++i) {
        for (int j = 0; j <= v; ++j) {
            if (j < i) dp[i][j] = -INF;
            else if (dp[i][j-1] > dp[i-1][j-1] + value[i-1][j-1]) {
                dp[i][j] = dp[i][j-1], lastPos[i][j] = lastPos[i][j-1];
            } else {
                dp[i][j] = dp[i-1][j-1] + value[i-1][j-1], lastPos[i][j] = j;
            }
        }
    }
    cout << dp[f][v] << endl;
    vector<int> a;
    for (int i = f, j = v; i; j = lastPos[i--][j]-1) a.push_back(lastPos[i][j]);
    for (int i = f-1; i >= 0; --i) cout << a[i] << ' ';
    cout << endl;
    return 0;
}