# include <iostream>
# include <fstream>
# include <vector>
# define MIN_INF -1000000000
int ** alloc_matrix ( int , int ) ;
void free_matrix ( int ** , int ) ;
void read_data ( std :: istream & , int & ) ;
void read_matrix ( std :: istream & , int , int , int ** ) ;
void print_matrix ( std :: ostream & , int , int , int ** ) ;
// backtracking
void init ( int , std :: vector <int > & ) ;
int succesor ( int , std :: vector <int> & , int , int ) ;
int suma ( int , int , int ** , std :: vector <int> ) ;
void bt ( int & , int ** , int , int ) ;
int main () {
std :: ifstream f ( "filip.in" ) ;
std :: ofstream g ( "filip.out" ) ;
int N ;
int M ;
int ** matrix ;
int max ;
read_data ( f , N ) ;
read_data ( f , M ) ;
matrix = alloc_matrix ( N , M ) ;
read_matrix ( f , N , M , matrix ) ;
bt ( max , matrix , N , M ) ;
g << max << '\n' ;
free_matrix ( matrix , N ) ;
f.close () ;
g.close () ;
return 0 ;
}
void bt ( int & max , int ** matrix , int N , int M ) {
int k = 0 ;
int as = 1 ;
std :: vector <int> array(2) ;
max = MIN_INF ;
int local ;
init (k , array ) ;
while ( k >= 0 ) {
as = succesor ( k , array , N , M ) ;
if ( as ) {
if ( k == 1 ) {
local = suma ( N , M , matrix , array ) ;
if ( local > max ) {
max = local ;
}
} else {
k ++ ;
init ( k , array ) ;
}
} else {
k -- ;
}
}
}
int suma ( int N , int M , int ** matrix , std :: vector <int> array ) {
int suma = 0 ;
for ( int i = 0 ; i < N ; i ++ ) {
for ( int j = 0 ; j < M ; j ++ ) {
if ( i == array[0] && j == array[1] ) {
suma += matrix[i][j] ;
} else if ( i == array[0] || j == array[1] ) {
suma += matrix[i][j] * ( -1 ) ;
} else {
suma += matrix[i][j] ;
}
}
}
return suma ;
}
int succesor ( int k , std :: vector <int> & array , int N , int M ) {
if ( k == 0 && array[k] < N - 1 ) {
array[k] ++ ;
return 1 ;
}
if ( k == 1 && array[k] < M - 1 ) {
array[k] ++ ;
return 1 ;
}
return 0 ;
}
void init ( int k , std :: vector <int> & array ) {
array[k] = -2 ;
}
void print_matrix ( std :: ostream & g , int N , int M , int ** matrix ) {
for ( int i = 0 ; i < N ; i ++ ) {
for ( int j = 0 ; j < M ; j ++ ) {
g << matrix[i][j] << ' ' ;
}
g << '\n' ;
}
}
void read_matrix ( std :: istream & f , int N , int M , int **matrix ) {
for ( int i = 0 ; i < N ; i ++ ) {
for ( int j = 0 ; j < M ; j ++ ) {
f >> matrix[i][j] ;
}
}
}
void read_data ( std :: istream & f , int & a ) {
f >> a ;
}
void free_matrix ( int ** matrix , int N ) {
for ( int i = 0 ; i < N ; i ++ ) {
delete [] matrix[i] ;
}
delete [] matrix ;
}
int ** alloc_matrix ( int N , int M ) {
int ** matrix ;
matrix = new int * [N] ;
for ( int i = 0 ; i < N ; i ++ ) {
matrix[i] = new int [M] ;
}
return matrix ;
}
Grosu Codrut-Cristian codrut_grosu