Cod sursa(job #1740385)

Utilizator jurjstyleJurj Andrei jurjstyle Data 11 august 2016 15:38:00
Problema Jocul Flip Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.37 kb
#include <fstream>

using namespace std ;

ifstream f ("flip.in") ;
ofstream g ("flip.out") ;

int n , m , a[18][18] , b[18][18] ;
int linii[18] , coloane[18] ;
long long smax = -1e9 ;

void verif ()
{
  for ( int i = 1 ; i <= m ; ++i )
    if ( coloane[i] )
        for ( int j = 1 ; j <= n ; ++j )
            a[j][i] *= -1 ;
 long long s = 0 ;
 for ( int i = 1 ; i <= n ; ++i )
    for ( int j = 1 ; j <= m ; ++j )
        s += a[i][j] ;

 if ( s > smax )
    smax = s ;
 for ( int i = 1 ; i <= n ; ++i )
    for ( int j = 1 ; j <= m ; ++j )
        a[i][j] = b[i][j] ;
 for ( int j = 1 ; j <= m ; ++j )
    coloane[j] = 0 ;
}

void calc_col ()
{
 for ( int i = 1 ; i <= n ; ++i )
    if ( linii[i] )
        for ( int j = 1 ; j <= m ; ++j )
            a[i][j] *= -1 ;
 for ( int j = 1 ; j <= m ; ++j )
    {
     long long s = 0 ;
     for ( int i = 1 ; i <= n ; ++i )
        s += a[i][j] ;
     if ( s < 0 )
        coloane[j] = 1 ;
    }
 verif () ;
}

void back1 ( int k )
{
 if ( k == n + 1 )
    calc_col () ;
 else
    {
     linii[k] = 0 ;
     back1 ( k + 1 ) ;
     linii[k] = 1 ;
     back1 ( k + 1 ) ;
     linii[k] = 0 ;
    }
}



int main ()
{
 f >> n >> m ;
 for ( int i = 1 ; i <= n ; ++i )
    for ( int j = 1 ; j <= m ; ++j )
        f >> a[i][j] , b[i][j] = a[i][j] ;
 back1 ( 1 ) ;
 g << smax ;

}