#include #include using namespace std; #define NMAX 1005 int a[NMAX][NMAX],n,sol = -1000000000; int d[NMAX][2],newd[NMAX][2],vmax; int ss[NMAX][NMAX],sd[NMAX][NMAX]; int main () { int i,j; // freopen("a.in","r",stdin); // freopen("a.out","w",stdout); scanf("%d",&n); for(i = 1; i <= n; i++) for(j = 1; j <= n; j++) { scanf("%d",&a[i][j]); ss[i][j] = ss[i][j - 1] + a[i][j]; } for(i = 1; i <= n; i++) for(j = n; j >= 1; j--) sd[i][j] = sd[i][j + 1] + a[i][j]; for(i = 1; i <= n; i++) { //printf("Linia %d\n",i); for(j = 1; j <= n; j++) newd[j][1] = max(d[j][1],0); for(j = n; j >= 1; j--) newd[j][0] = max(d[j][0],0); vmax = 0; for(j = 1; j <= n; j++) { newd[j][1] = max(newd[j][1] + a[i][j], ss[i][j] + vmax); vmax = max(vmax, d[j][0] - ss[i][j - 1]); } vmax = 0; for(j = n; j >= 1; j--) { newd[j][0] = max(newd[j][0] + a[i][j], sd[i][j] + vmax); vmax = max(vmax, d[j][1] - sd[i][j + 1]); } for(j = 1; j <= n; j++) { // printf("%d %d %d\n",j,newd[j][0],newd[j][1]); d[j][0] = newd[j][0]; d[j][1] = newd[j][1]; sol = max(sol, d[j][0]); sol = max(sol, d[j][1]); } } printf("%d\n",sol); return 0; }