//Problem b from mindcodingFinalRound2 //"We are drowning in information and starved for knowledge." #include #include #include #include #include #include using namespace std; #define int64 long long const int inf = 0x3f3f3f3f, kMaxN = 1005; int el[kMaxN][kMaxN]; int st[kMaxN], dr[kMaxN]; int dp[kMaxN][kMaxN]; int main() { ios::sync_with_stdio(false); int n; cin >> n; for (int i = 1; i <= n; ++i) { for (int j = 1; j <= n; ++j) { cin >> el[i][j]; } } int mx = -inf; for (int l = 1; l <= n; ++l) { for (int c = 1; c <= n; ++c) { dr[c] = max(dr[c - 1], dp[l - 1][c]) + el[l][c]; } for (int c = n; c; --c) { st[c] = max(st[c + 1], dp[l - 1][c]) + el[l][c]; dp[l][c] = max(st[c], dr[c]); mx = max(dp[l][c], mx); dp[l][c] = max(0, dp[l][c]); } } cout << mx << '\n'; return 0; }