#include #define INF 1000100000 using namespace std; int n, mat[1010][1010], sol; int best[4][1010][1010]; /// 0 = L -> 0, 2 /// 1 = R -> 1, 3 /// 2 = LD -> 2, 1 /// 3 = RD -> 3, 0 int main() { //freopen("B.in", "r", stdin); int i, j; cin >> n; for(i = 1; i <= n; ++i) for(j = 1; j <= n; ++j) cin >> mat[i][j]; for(i = 0; i <= n + 1; ++i) for(j = 0; j <= n + 1; ++j) best[0][i][j] = best[1][i][j] = best[2][i][j] = best[3][i][j] = -INF; for(i = 1; i <= n; ++i) { for(j = 1; j <= n; ++j) best[0][i][j] = best[1][i][j] = best[2][i][j] = best[3][i][j] = mat[i][j]; for(j = 1; j <= n; ++j) { best[2][i][j] = max(best[2][i][j], best[2][i - 1][j] + mat[i][j]); best[2][i][j] = max(best[2][i][j], best[0][i - 1][j] + mat[i][j]); best[3][i][j] = max(best[3][i][j], best[3][i - 1][j] + mat[i][j]); best[3][i][j] = max(best[3][i][j], best[1][i - 1][j] + mat[i][j]); } for(j = 1; j <= n; ++j) { best[0][i][j] = max(best[0][i][j], best[0][i][j - 1] + mat[i][j]); best[0][i][j] = max(best[0][i][j], best[3][i][j - 1] + mat[i][j]); } for(j = n; j > 0; --j) { best[1][i][j] = max(best[1][i][j], best[1][i][j + 1] + mat[i][j]); best[1][i][j] = max(best[1][i][j], best[2][i][j + 1] + mat[i][j]); } } sol = -INF; for(i = 1; i <= n; ++i) for(j = 1; j <= n; ++j) { sol = max(sol, max(best[0][i][j], best[1][i][j])); sol = max(sol, max(best[2][i][j], best[3][i][j])); } cout << sol << "\n"; return 0; }