#include #include #include using namespace std; const int INF = 0x3f3f3f3f; int N; int A[1002][1002]; int maxgo[1002][1002][4]; // 0 - L, 1 - DR, 2 - R, 3 - DL int getMax(int i, int j, int p) { if (i < 1 || i > N || j < 1 || j > N) return 0; int &now = maxgo[i][j][p]; if (now != -INF) return now; if (p == 0) { now = max(now, A[i][j] + getMax(i, j - 1, 0)); now = max(now, A[i][j] + getMax(i, j - 1, 1)); } else if (p == 1) { now = max(now, A[i][j] + getMax(i + 1, j, 1)); now = max(now, A[i][j] + getMax(i + 1, j, 2)); } else if (p == 2) { now = max(now, A[i][j] + getMax(i, j + 1, 2)); now = max(now, A[i][j] + getMax(i, j + 1, 3)); } else { now = max(now, A[i][j] + getMax(i + 1, j, 3)); now = max(now, A[i][j] + getMax(i + 1, j, 0)); } return now; } int main() { cin >> N; for (int i = 1; i <= N; ++i) for (int j = 1; j <= N; ++j) cin >> A[i][j]; for (int i = 1; i <= N; ++i) for (int j = 1; j <= N; ++j) for (int k = 0; k < 4; ++k) maxgo[i][j][k] = -INF; int result = -INF; for (int i = 1; i <= N; ++i) for (int j = 1; j <= N; ++j) { result = max(result, getMax(i, j, 0)); result = max(result, getMax(i, j, 1)); result = max(result, getMax(i, j, 2)); result = max(result, getMax(i, j, 3)); } cout << result << '\n'; }