Cod sursa(job #438399)

Utilizator Pepelea_FlaviuFlaviu Pepelea Pepelea_Flaviu Data 10 aprilie 2010 18:38:44
Problema Jocul Flip Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.16 kb
# include <cstdio>

using namespace std;

# define FIN "flip.in"
# define FOUT "flip.out"
# define max(a, b) ((a) > (b) ? (a) : (b))
# define MAX_N 20

int N, M, i, j, sol;
int s[MAX_N];
int A[MAX_N][MAX_N];

    void verif() {
        int i, j, sum = 0, aux;
        
        for (i = 1; i <= N; ++i)
           for (j = 1; j <= M; ++j)
              s[i] ? sum -= A[i][j] : sum += A[i][j];
              
        for (j = 1; j <= M; ++j) {
            aux = 0;
            for (i = 1; i <= N; ++i)
               s[i] ? aux -= A[i][j] : aux += A[i][j];
            if (aux < 0) sum += 2 * (-aux);
        }
        sol = max(sol, sum);
    }

    void back(int k)
    {
        for (int i = 0; i <= 1; ++i) {
            s[k] = i;
            k < N ? back(k + 1) : verif();
        }
    }

    int main() {
        freopen(FIN, "r", stdin);
        freopen(FOUT, "w", stdout);
        
        scanf("%d%d", &N, &M);
        for (i = 1; i <= N; ++i)
           for (j = 1; j <= M; ++j)
              scanf("%d", &A[i][j]), sol += A[i][j];
        
        back(1);
        
        printf("%d", sol);
        
        return 0;
    }