#include #include #include #include #include #include #define maxn 1010 using namespace std; ifstream fin("test.in"); ofstream fout("test.out"); int n; long long a[maxn][maxn],best[maxn][maxn][2],dp[maxn][maxn][2],answer; 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) dp[i][j][0] = dp[i][j][1] = a[i][j]; } for (int i = 1; i <= n; ++i) { for (int j = 1; j <= n; ++j) { dp[i][j][0] = max(dp[i][j][0], best[i-1][j][1] + a[i][j]); dp[i][j][1] = max(dp[i][j][1], best[i-1][j][0] + a[i][j]); } for (int j = 1; j < n; ++j) { dp[i][j+1][0] = max(dp[i][j+1][0], dp[i][j][0] + a[i][j+1]); } for (int j = n; j > 1; --j) { dp[i][j-1][1] = max(dp[i][j-1][1], dp[i][j][1] + a[i][j-1]); } for (int j = 1; j <= n; ++j) { best[i][j][0] = max(a[i][j], best[i-1][j][0] + a[i][j]); if (j != 1) best[i][j][0] = max(best[i][j][0], dp[i][j-1][0] + a[i][j]); best[i][j][1] = max(a[i][j], best[i-1][j][1] + a[i][j]); if (j != n) best[i][j][1] = max(best[i][j][1], dp[i][j+1][1] + a[i][j]); answer = max(answer, dp[i][j][0]); answer = max(answer, dp[i][j][1]); } } cout << answer; }