105335K - Kid Rally

#ifndef MyGO
#define MyGO
#include MyGO __FILE__ MyGO

void chmax(int& x, int y) {
    if (x < y)
        x = y;
}

signed main() {
    fast;

    int n, m;
    cin >> n >> m;
    vector<vector<int>> mp(n, vector<int>(m));
    for (int i = 0; i < n; i++) for (int j = 0; j < m; j++)
        cin >> mp[i][j];

    vector<int> mx(n), suf(n, 0);
    for (int i = n-1; i > 0; i--) {
        for (int j = 0; j < m; j++)
            chmax(mx[i], mp[i][j]);
        suf[i-1] = suf[i] + mx[i];
    }


    int k = n*9+1;
    vector<int> dp(k, -1), pdp;
    dp[mp[0][0]] = mp[0][m-1];
    int ans = max(
        (mp[0][0]+suf[0])*mp[0][m-1],
        mp[0][0]*(suf[0]+mp[0][m-1])
    );
    for (int i = 1; i < n; i++) {
        pdp = dp;
        int s = mp[i].back();
        array<int,10> tt{};
        tt.fill(-1);
        for (int j = m-2; j >= 0; j--) {
            auto v = mp[i][j];
            chmax(tt[v], s);
            s = max(s, v);
        }
        for (int v = 0; v < 10; v++) if (tt[v] != -1)
            for (int r = 0; r+v < k; r++)
                if (pdp[r] != -1)
                    chmax(dp[r+v], pdp[r]+tt[v]);
        int o = suf[i];
        for (int r = 0; r < k; r++) if (dp[r] != -1)
            chmax(ans, max(dp[r] * (r+o), (dp[r]+o) * r));
    }
    cout << ans << endl;

    return 0;
}

#else

#include <bits/stdc++.h>
using namespace std;

#ifdef DEBUG
#define fast
#define safe cerr<<__PRETTY_FUNCTION__<<" line "<<__LINE__<<" safe\n"
#else
#define fast cin.tie(0)->sync_with_stdio(0)
#endif

using ll = long long;

#endif