# CFR 429 B. Working out ( DP )

Problem - B - Codeforces

int N, M;
vvi A;

void init(){
cin >> N >> M;
A = vvi( N, vi( M ) );
for( int i = 0; i < N; ++i )
for( int j = 0; j < M; ++j )
cin >> A[ i ][ j ];
}

vvi dpq, dpp, dpz, dpm;

void preprocess(){
dpq = dpp = dpz = dpm = vvi( N, vi( M + 1 ) );
dpq[ 0 ][ 0 ] = A[ 0 ][ 0 ];
for( int i = 0; i < N; ++i )
for( int j = 0; j < M; ++j ){
if( i + 1 < N )
upmax( dpq[ i + 1 ][ j ], dpq[ i ][ j ] + A[ i + 1 ][ j ] );
if( j + 1 < M )
upmax( dpq[ i ][ j + 1 ], dpq[ i ][ j ] + A[ i ][ j + 1 ] );
}
dpp[ 0 ][ M - 1 ] = A[ 0 ][ M - 1 ];
for( int i = 0; i < N; ++i )
for( int j = M - 1; j >= 0; --j ){
if( i + 1 < N )
upmax( dpp[ i + 1 ][ j ], dpp[ i ][ j ] + A[ i + 1 ][ j ] );
if( j - 1 >= 0 )
upmax( dpp[ i ][ j - 1 ], dpp[ i ][ j ] + A[ i ][ j - 1 ] );
}
dpz[ N - 1 ][ 0 ] = A[ N - 1 ][ 0 ];
for( int i = N - 1; i >= 0; --i )
for( int j = 0; j < M; ++j ){
if( i - 1 >= 0 )
upmax( dpz[ i - 1 ][ j ], dpz[ i ][ j ] + A[ i - 1 ][ j ] );
if( j + 1 < M )
upmax( dpz[ i ][ j + 1 ], dpz[ i ][ j ] + A[ i ][ j + 1 ] );
}
dpm[ N - 1 ][ M - 1 ] = A[ N - 1 ][ M - 1 ];
for( int i = N - 1; i >= 0; --i )
for( int j = M - 1; j >= 0; --j ){
if( i - 1 >= 0 )
upmax( dpm[ i - 1 ][ j ], dpm[ i ][ j ] + A[ i - 1 ][ j ] );
if( j - 1 >= 0 )
upmax( dpm[ i ][ j - 1 ], dpm[ i ][ j ] + A[ i ][ j - 1 ] );
}
}

void solve(){
int ans = 0;
for( int i = 1; i + 1 < N; ++i )
for( int j = 1; j + 1 < M; ++j )
upmax( ans, dpq[ i - 1 ][ j ] + dpp[ i ][ j + 1 ] + dpz[ i ][ j - 1 ] + dpm[ i + 1 ][ j ] ),
upmax( ans, dpq[ i ][ j - 1 ] + dpp[ i - 1 ][ j ] + dpz[ i + 1 ][ j ] + dpm[ i ][ j + 1 ] );
cout << ans << endl;
}