题解

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

const long long min_ll = -1e18;

int n, m;
long long w[1010][1010];
long long f[1010][1010][2];

inline long long mx(long long p, long long q, long long r) {
    return p > q ? (p > r ? p : r) : (q > r ? q : r);
}

long long dfs(int x, int y, int from) {
    if (x < 1 || x > n || y < 1 || y > m) {
        return min_ll;
    }
    if (f[x][y][from] != min_ll) {
        return f[x][y][from];
    }
    if (from == 0) {
        f[x][y][from] = mx(dfs(x + 1, y, 0), dfs(x, y - 1, 0), dfs(x, y - 1, 1)) + w[x][y];
    } else {
        f[x][y][from] = mx(dfs(x - 1, y, 1), dfs(x, y - 1, 0), dfs(x, y - 1, 1)) + w[x][y];
    }
    return f[x][y][from];
}

int main() {
    cin >> n >> m;
    
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            cin >> w[i][j];
            f[i][j][0] = f[i][j][1] = min_ll;
        }
    }
    
    f[1][1][0] = f[1][1][1] = w[1][1];
    
    cout << dfs(n, m, 1) << endl;
    
    return 0;
}