#include #include using namespace std; int n,ok,Max,A[1005][1005],L[1005][1005],R[1005][1005],DL[1005][1005],DR[1005][1005]; void afis(int V[1005][1005], int DIM) { int i,j; for (i=1;i<=DIM;++i) { for (j=1;j<=DIM;++j) cout<>n; for (i=1;i<=n;++i) for (j=1;j<=n;++j) cin>>A[i][j]; Max=A[1][1]; for (i=1;i<=n;++i) { for (j=1;j<=n;++j) { DL[i][j]=A[i][j], DR[i][j]=A[i][j]; DL[i][j]=max(DL[i][j],R[i-1][j]+A[i][j]); if (i>0) DL[i][j]=max(DL[i][j],DL[i-1][j]+A[i][j]); DR[i][j]=max(DR[i][j],L[i-1][j]+A[i][j]); if (i>0) DR[i][j]=max(DR[i][j],DR[i-1][j]+A[i][j]); } for (j=1;j<=n;++j) { R[i][j]=A[i][j]; if (j>1) R[i][j]=max(R[i][j],R[i][j-1]+A[i][j]); if (i>1) R[i][j]=max(R[i][j],DR[i-1][j]+A[i][j]); R[i][j]=max(R[i][j],DR[i][j-1]+A[i][j]); R[i][j]=max(R[i][j],L[i-1][j]+A[i][j]); } for (j=n;j>0;--j) { L[i][j]=A[i][j]; if (j1) L[i][j]=max(L[i][j],DL[i-1][j]+A[i][j]); L[i][j]=max(L[i][j],DL[i][j+1]+A[i][j]); L[i][j]=max(L[i][j],R[i-1][j]+A[i][j]); } } for (i=1;i<=n;++i) for (j=1;j<=n;++j) { Max=max(Max,R[i][j]); Max=max(Max,L[i][j]); Max=max(Max,DL[i][j]); Max=max(Max,DR[i][j]); } cout<