#include using namespace std; #define ll long long #define MAXN 1000 int mat[1001][1001]; int dp[1001][1001][4]; #define INF 2000000000 int n; #define FROM_LEFT 0 #define FROM_RIGHT 1 #define FROM_TOP_LEFT 2 #define FROM_TOP_RIGHT 3 ll f(int i, int j, int k){ if(dp[i][j][k]!=-INF) return dp[i][j][k]; if(i<0 || i>=n || j<0 || j>=n) return -INF; if(k == FROM_LEFT && j==0 || k == FROM_RIGHT && j==n-1 || i==0 &&(k== FROM_TOP_LEFT || k== FROM_TOP_RIGHT)){ return dp[i][j][k] = mat[i][j]; } if(k == FROM_LEFT){ return dp[i][j][k] = max(f(i, j-1, FROM_LEFT), f(i, j-1, FROM_TOP_RIGHT)) + mat[i][j]; } if(k == FROM_RIGHT){ return dp[i][j][k] = max(f(i, j+1, FROM_RIGHT), f(i, j+1, FROM_TOP_LEFT)) + mat[i][j]; } if(k == FROM_TOP_LEFT){ return dp[i][j][k] = max(f(i-1, j, FROM_TOP_LEFT), f(i-1, j, FROM_LEFT)) + mat[i][j]; } if(k == FROM_TOP_RIGHT){ return dp[i][j][k] = max(f(i-1, j, FROM_TOP_RIGHT), f(i-1, j, FROM_RIGHT)) + mat[i][j]; } } int main() { //freopen("C:\\in.txt", "r", stdin); scanf("%d", &n); for(int i=0; i