#include #include #include #include #include using namespace std; //ifstream fin("date.in"); //ofstream fout("date.out"); //#define cout fout #define MAX 1002 int a[MAX][MAX]; int josl[MAX][MAX]; //daca va merge in jos si apoi la stanga int josr[MAX][MAX]; // daca va merge in jos si apoi la dreapta int l[MAX][MAX]; // daca va merge in stanga int r[MAX][MAX]; // dava va merge in dreapta int main() { int n, i, j, mx = -10000; cin >> n; for(i = 1 ; i <= n ; i++) { for(j = 1 ; j <= n ; j++) { cin >> a[i][j]; } } for(i = n ; i >= 1 ; i--) { for(j = 1 ; j <= n ; j++) { josl[i][j] = max(josl[i + 1][j], max(l[i + 1][j], a[i + 1][j])) + a[i][j]; josr[i][j] = max(josr[i + 1][j], max(r[i + 1][j], a[i + 1][j])) + a[i][j]; l[i][j] = max(l[i][j - 1], max(josr[i][j - 1], a[i][j - 1])) + a[i][j]; } for(j = n ; j>= 1 ; j--) { r[i][j] = max(r[i][j + 1], max(josl[i][j + 1], a[i][j + 1])) + a[i][j]; mx = max(max(mx, a[i][j]), max(l[i][j], max(r[i][j], max(josl[i][j], josr[i][j])))); } } cout << mx << "\n"; }