#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; const int INF = 0x3f3f3f3f; const double EPS = 0.000000001; const double PI = 3.141592653589793; const long long LLINF = 99999999999999999LL; const int MAX_N = 1002; int N; int A[MAX_N][MAX_N], D[MAX_N][MAX_N][3], sumLeft[MAX_N][MAX_N], sumRight[MAX_N][MAX_N]; int bestL[MAX_N], bestR[MAX_N]; 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) { sumLeft[i][j] = sumLeft[i][j - 1] + A[i][j]; } for(int j = N; j >= 1; --j) { sumRight[i][j] = sumRight[i][j + 1] + A[i][j]; } } for(int j = 1; j <= N; ++j) { D[1][j][0] = A[1][j]; } int minVal = 0; for(int j = 1; j <= N; ++j) { D[1][j][1] = sumLeft[1][j] - minVal; minVal = min(minVal, sumLeft[1][j]); } minVal = 0; for(int j = N; j >= 1; --j) { D[1][j][2] = sumRight[1][j] - minVal; minVal = min(minVal, sumRight[1][j]); } for(int i = 2; i <= N; ++i) { for(int j = 1; j <= N; ++j) { D[i][j][0] = max(D[i - 1][j][0], max(D[i - 1][j][1], D[i - 1][j][2])) + A[i][j]; } D[i][1][1] = -INF; for(int j = 2; j <= N; ++j) { D[i][j][1] = max(D[i][j - 1][0], D[i][j - 1][1]) + A[i][j]; } D[i][N][2] = -INF; for(int j = N - 1; j >= 1; --j) { D[i][j][2] = max(D[i][j + 1][0], D[i][j + 1][2]) + A[i][j]; } } int ans = A[1][1]; for(int i = 1; i <= N; ++i) { for(int j = 1; j <= N; ++j) { for(int k = 0; k < 3; ++k) { ans = max(ans, D[i][j][k]); } } } cout << ans; return 0; }