#include using namespace std; #define ll long long #define MAXN 1000 int a,b,n,m,p,k; int arr[MAXN]; #define N_INF -999999 ll mat[1001][1001]; ll dp[1001][1001][3]; ll f(int i, int j, int k){ if(i<0 || j<0 || j>=n || i>=n) return N_INF; if(dp[i][j][k]!=N_INF) return dp[i][j][k]; if(i==0 && k==1){ return dp[i][j][1] = mat[i][j]; } if(j==0 && k==0){ return dp[i][j][0] = mat[i][j]; } if(j==n-1 && k==2){ return dp[i][j][2] = mat[i][j]; } ll res = N_INF; if(k==0){ return dp[i][j][k] = max(mat[i][j], max(f(i, j-1, 1), f(i, j-1, 0))+mat[i][j]); } if(k==1){ return dp[i][j][k] = max(mat[i][j], max(f(i-1, j, 0), max(f(i-1, j, 2), f(i-1, j, 1)))+mat[i][j]); } if(k==2){ return dp[i][j][k] = max(mat[i][j], max(f(i, j+1, 2), f(i, j+1, 1))+mat[i][j]); } } int main() { ios_base::sync_with_stdio(false); // freopen("C:\\in.txt", "r", stdin); cin >> n; for(int i=0; i> mat[i][j]; } } for(int i=0; i