Cod sursa(job #2145720)

Utilizator IulianOleniucIulian Oleniuc IulianOleniuc Data 27 februarie 2018 16:13:19
Problema Jocul Flip Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.88 kb
#include <fstream>
#define DMAX 20

std::ifstream fin("flip.in");
std::ofstream fout("flip.out");

int m, n;
int mat[DMAX][DMAX];

int sol;
int inv[DMAX];

void bkt(int pos) {
    if (pos == m + 1) {
        int sum = 0;
        for (int j = 1; j <= n; j++) {
            int sumCol = 0;
            for (int i = 1; i <= m; i++)
                sumCol += mat[i][j] * inv[i];

            if (sumCol < 0)
                sum -= sumCol;
            else
                sum += sumCol;
        }

        if (sum > sol)
            sol = sum;
        return;
    }

    inv[pos] = -1;
    bkt(pos + 1);

    inv[pos] = +1;
    bkt(pos + 1);
}

int main() {
    fin >> m >> n;
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            fin >> mat[i][j];

    bkt(1);
    fout << sol << '\n';

    fout.close();
    return 0;
}