## Editorial for Đường đi có tổng lớn nhất

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

#### Code mẫu của flashmt

var a,b:array[0..101,1..100] of integer;
n,m:byte;

procedure rf;
var i,j:byte;
begin
for i:=1 to m do
begin
for j:=1 to n do
end;
end;

function max(a,b,c:integer):integer;
begin
if (a>=b) and (a>=c) then max:=a
else
begin
if b>c then max:=b else max:=c;
end;
end;

procedure pr;
var i,j:byte;
begin
fillchar(b,sizeof(b),0);
for j:=1 to n do
begin
b[0,j]:=-30000;
b[n+1,j]:=b[0,j];
end;
for i:=1 to m do
b[i,1]:=a[i,1];
for j:=2 to n do
for i:=1 to m do
b[i,j]:=max(b[i-1,j-1],b[i,j-1],b[i+1,j-1])+a[i,j];
end;

procedure wf;
var  i:byte; max:integer;
begin
max:=-32000;
for i:=1 to m do
if b[i,n]>max then max:=b[i,n];
write(max);
end;

begin
rf;
pr;
wf;
end.


#### Code mẫu của happyboy99x

#include <cstdio>
#include <queue>
#include <climits>
#include <algorithm>
using namespace std;

#define INF 1000000000
#define REP(i, n) for( int i = 0, _n = (n); i < _n; ++i )
#define F(j, i) (j >= 0 && j < n && i >= 0 && i < m ? f[j][i] : -INF)
typedef pair<int, int> ii;

int a[105][105], f[105][105];
int m, n;

int main() {
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);
#endif
scanf("%d%d", &m, &n);
REP(i, m) REP(j, n) scanf("%d", &a[i][j]);
REP(i,m) f[0][i] = a[i][0];
for(int j=1; j<n; ++j)
for(int i = 0; i < m; ++i)
f[j][i] = a[i][j] + max(F(j-1,i-1),max(F(j-1,i+1),F(j-1,i)));
int res = INT_MIN;
REP(i,m) res = max(res, f[n-1][i]);
printf( "%d\n", res );
return 0;
}


program qbmax;
uses    math;
const   fi='';
var     a,tong:array[0..101,0..101] of longint;
check:array[0..101,0..101] of boolean;
res,m,n,i,minA:longint;
inp:text;
procedure input;
var     i,j:longint;
begin
assign(inp,fi);
reset(inp);
for i:=1 to m do
begin
for j:=1 to n do
begin
minA:=min(a[i,j],minA);
end;
end;
close(inp);
end;

function qhd(i,j:longint):longint;
var     temp:longint;
begin

if check[i,j] then exit(tong[i,j]);

temp:=qhd(i-1,j-1);
temp:=max(temp,qhd(i,j-1));
temp:=max(temp,qhd(i+1,j-1));

tong[i,j]:=temp+a[i,j];
check[i,j]:=true;
exit(tong[i,j]);
end;

procedure init;
var     i:longint;
begin
for i:=0 to n+1 do begin
tong[0,i]:=low(integer);
check[0,i]:=true;
tong[m+1,i]:=low(integer);
check[m+1,i]:=true;
end;

for i:=1 to m do
begin
tong[i,0]:=low(integer);
check[i,0]:=true;
tong[i,n+1]:=low(integer);
check[i,n+1]:=true;
end;
for i:=1 to m do
begin
tong[i,1]:=a[i,1];
check[i,1]:=true;
end;

end;

begin
input;
init;
res:=low(longint);
for i:=1 to m do
res:=max(res,qhd(i,n));
write(res);
end.


#### Code mẫu của RR

{$R+,Q+} uses math; var a,f:array[-1..111,-1..111] of longint; m,n,i,j:longint; begin read(m,n); for i:=1 to m do for j:=1 to n do read(a[i,j]); fillchar(f,sizeof(f),$80);
for i:=1 to m do
f[i,1]:=a[i,1];

for j:=2 to n do
for i:=1 to m do
f[i,j]:=max(max(f[i-1,j-1],f[i,j-1]),f[i+1,j-1])+a[i,j];

j:=-1000111000;
for i:=1 to m do
j:=max(j,f[i,n]);
writeln(j);
end.


#### Code mẫu của hieult

#include <stdio.h>
//#include <conio.h>
main()
{
int n,m,a[102][102],b[102][102],max,max1=-10000;
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d",&a[i][j]);
for(int j=1;j<=m;j++)
{ b[0][j]=-10000; b[n+1][j]=-10000; }
for(int i=1;i<=n;i++)
b[i][1]=a[i][1];
for(int j=2;j<=m;j++)
for(int i=1;i<=n;i++)
{
if(b[i-1][j-1]>b[i][j-1])
max=b[i-1][j-1];
else max=b[i][j-1];
if(max<b[i+1][j-1])
max=b[i+1][j-1];
b[i][j]=max+a[i][j];
}
for(int i=1;i<=n;i++)
if(b[i][m]>max1)
max1=b[i][m];
printf("%d",max1);
//getch();
}


#### Code mẫu của ll931110

Program QBMAX;
Const
input  = '';
output = '';
Var
A,B: array[0..200,0..200] of longint;
m,n: longint;

Procedure init;
Var
f: text;
i,j: longint;
Begin
Assign(f, input);
Reset(f);
For i:= 1 to m do
For j:= 1 to n do read(f, A[i,j]);
Close(f);
End;

Procedure optimize;
Var
f: text;
i,j,s: longint;
Begin
For i:= 0 to n do
Begin
B[0,i]:= -1000000000;
B[m + 1,i]:= -1000000000;
End;
For i:= 1 to m do B[i,1]:= A[i,1];

For j:= 2 to n do
For i:= 1 to m do
Begin
B[i,j]:= B[i - 1,j - 1];
If B[i,j] < B[i,j - 1] then B[i,j]:= B[i,j - 1];
If B[i,j] < B[i + 1,j - 1] then B[i,j]:= B[i + 1,j - 1];
B[i,j]:= B[i,j] + A[i,j];
End;

s:= B[1,n];
For i:= 2 to m do if s < B[i,n] then s:= B[i,n];

Assign(f, output);
Rewrite(f);
Writeln(f, s);
Close(f);
End;

Begin
init;
optimize;
End.