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