Pagini recente » Cod sursa (job #1090217) | Cod sursa (job #2846825) | Cod sursa (job #2293900) | Cod sursa (job #295675) | Cod sursa (job #1437375)
#include <cstdio>
#include <algorithm>
using namespace std;
#define Nmax 18
#define inf 0x3f3f3f3f
FILE *f = fopen ( "flip.in", "r" );
FILE *g = fopen ( "flip.out", "w" );
int v[Nmax][Nmax], N, M, rez = -inf;
void TotalSum (){ //calc suma totala din matrice
int sum = 0;
for ( int i = 1; i <= N; ++i )
for ( int j = 1; j <= M; ++j )
sum += v[i][j];
rez = max ( rez, sum ); // si actualizez maximul
}
//flipuiesc linia ind
void FlipLine ( int ind ){
for ( int i = 1; i <= M; ++i )
v[ind][i] *= -1;
}
//flipuiesc coloana ind
void FlipCol ( int ind ){
for ( int i = 1; i <= N; ++i )
v[i][ind] *= -1;
}
//fac suma pe coloana ind
int SumaCol ( int ind ){
int sum = 0;
for ( int i = 1; i <= N; ++i )
sum += v[i][ind];
return sum;
}
//flipuiesc coloanele cu suma negativa
void CheckCols (){
for ( int i = 1; i <= M; ++i )
if ( SumaCol ( i ) < 0 )
FlipCol(i);
}
//generez toate modalitatile de a flipui linii si ajustez coloanele dupa ele
void Back ( int line ){
for ( int i = 0; i <= 1; ++i ){
if ( !i ){ // NU flipuiesc linia line
CheckCols(); //ajustez coloanele
TotalSum(); //verific daca e sol mai buna
if ( line < N )
Back ( line + 1 );
}
else{ // flipuiesc linia line
FlipLine ( line ); // flipuiesc linia
CheckCols();//ajustez coloanele
TotalSum();//verific daca e sol mai buna
if ( line < N )
Back ( line + 1 );
}
}
}
int main(){
fscanf ( f, "%d%d", &N, &M );
for ( int i = 1; i <= N; ++i )
for ( int j = 1; j <= M; ++j )
fscanf ( f, "%d", &v[i][j] );
fprintf ( g, "%d", rez );
return 0;
}