Giới thiệu
include <iostream>
include <vector>
include <algorithm>
using namespace std;
const int INF = -1e9;
int main() {
int N, M;
cin >> N >> M;
vector<vector<int>> grid(N + 1, vector<int>(M + 1));
for (int i = 1; i <= N; ++i) {
for (int j = 1; j <= M; ++j) {
cin >> grid[i][j];
}
}
vector<vector<vector<int>>> dp(N + 1, vector<vector<int>>(M + 1, vector<int>(N + 1, INF)));
dp[1][1][1] = 0;
for (int r1 = 1; r1 <= N; ++r1) {
for (int c1 = 1; c1 <= M; ++c1) {
for (int r2 = 1; r2 <= N; ++r2) {
int c2 = r1 + c1 - r2;
if (c2 < 1 || c2 > M) continue;
int current_max = INF;
if (r1 > 1 && r2 > 1) current_max = max(current_max, dp[r1 - 1][c1][r2 - 1]);
if (r1 > 1 && c2 > 1) current_max = max(current_max, dp[r1 - 1][c1][r2]);
if (c1 > 1 && r2 > 1) current_max = max(current_max, dp[r1][c1 - 1][r2 - 1]);
if (c1 > 1 && c2 > 1) current_max = max(current_max, dp[r1][c1 - 1][r2]);
if (current_max != INF) {
dp[r1][c1][r2] = current_max + grid[r1][c1];
if (r1 != r2 || c1 != c2) {
dp[r1][c1][r2] += grid[r2][c2];
}
}
}
}
}
cout << dp[N][M][N] << endl;
return 0;
}