//birocratie2 #4611
#include <iostream>
#include <fstream>
#include <cmath>
using namespace std;
string fisier="birocratie";
ifstream fin(fisier+".in");
ofstream fout(fisier+".out");
#define MINIM -1e9
#define Nmax 1001
int n, mat[Nmax][Nmax];
int dp[Nmax][Nmax];
/*
programare dinamica pe diagonale;
//
parcurgem pe rand toate diagonalele paralele cu cea secundara,
de sus in jos iar apoi de jos in sus; parcurgea in ambele directii
este pentru a verifica ca toate costurile sunt calculate optim,
fara sa conteze ordinea in care procesam elemente;
in cazul fiecarui element, vedem daca putem ajunge la el
prin una dintre celelalte 2 variante posibile de deplasare
(in jos sau la dreapta);
daca exista, alegem calea de castig maxim si o adunam elementului
curent;
*/
void citire()
{
 fin>>n;
 for (int i=1; i<=n; ++i) for (int j=1; j<=n; ++j) fin>>mat[i][j];
}
bool sunt_in_matrice(int i, int j)
{
 return i>=1 && i<=n && j>=1 && j<=n; } void rezolvare() { dp[1][1]=mat[1][1]; for(int diag=2; diag<=2*n-1; ++diag) { int suma=MINIM; for(int i=1; i<=n; ++i) { int j=diag-i+1; if(sunt_in_matrice(i,j)) { if(sunt_in_matrice(i-1,j)) { suma=max(suma,dp[i-1][j]); } if(sunt_in_matrice(i,j-1)) { suma=max(suma,dp[i][j-1]); } dp[i][j]=suma+mat[i][j]; suma+=mat[i][j]; } } suma=MINIM; for(int i=n; i>=1; --i)
 {
 int j=diag-i+1;
 if(sunt_in_matrice(i,j))
 {
 if(sunt_in_matrice(i-1,j))
 {
 suma=max(suma,dp[i-1][j]);
 }
 if(sunt_in_matrice(i,j-1))
 {
 suma=max(suma,dp[i][j-1]);
 }
 dp[i][j]=max(dp[i][j],suma+mat[i][j]);
 //vedem daca obtinem o imbunatatire fata
 //de prima parcurgere
 suma+=mat[i][j];
 }
 }
 }
 fout<<dp[n][n];
}
int main()
{
 citire();
 rezolvare();
 return 0;
}
</div><div class="naked_ctrl">
<form action="/index.cgi/contrast" method="get" name="gate">
<p><a href="http://altstyle.alfasado.net">AltStyle</a> によって変換されたページ <a href="https://pastebin.com/raw/iWqs3Tuk">(-&gt;オリジナル)</a>
/ <label>アドレス: <input type="text" name="naked_post_url" value="https://pastebin.com/raw/iWqs3Tuk" size="22" /></label> <label>モード: <select name="naked_post_mode">
<option value="default">デフォルト</option>
<option value="speech">音声ブラウザ</option>
<option value="ruby">ルビ付き</option>
<option value="contrast" selected="selected">配色反転</option>
<option value="larger-text">文字拡大</option>
<option value="mobile">モバイル</option>
</select>
<input type="submit" value="表示" />
</p>
</form>
</div>