Cod sursa(job #3263056)

Utilizator Mihai_PopescuMihai Popescu Mihai_Popescu Data 13 decembrie 2024 00:23:53
Problema Jocul Flip Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.44 kb
#include <fstream>
using namespace std;

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

#define INF 1e18

int a[20][20];
long long smax = -INF;

int subm[20];
bool uz1[20], uz2[20];

long long sum(int n, int m) {
    long long s = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            int semn = 1;
            if (uz1[i]) {
                semn *= -1;
            }
            if (uz2[j]) {
                semn *= -1;
            }
            s += semn * a[i][j];
        }
    }
    return s;
}

void back(int k, int n, int m) {
    for (int i = 1; i <= n; ++i) {
        if (!uz1[i]) {
            uz1[i] = 1;

            int s = sum(n, m);
            if (s > smax) {
                smax = s;
            }

            if (k < n) {
                back(k + 1, n, m);
            }

            uz1[i] = 0;
        }
    }
    for (int i = 1; i <= m; ++i) {
        if (!uz2[i]) {
            uz2[i] = 1;

            int s = sum(n, m);
            if (s > smax) {
                smax = s;
            }

            if (k < n) {
                back(k + 1, n, m);
            }

            uz2[i] = 0;
        }
    }
}

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

    back(1, n, m);

    fout << smax;
    return 0;
}