Cod sursa(job #2225092)

Utilizator BaldurCronos Baldur Data 25 iulie 2018 21:28:54
Problema Jocul Flip Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.17 kb
#include <iostream>
#include <fstream>
#define N 20
using namespace std;
ifstream in("flip.in");
ofstream out("flip.out");
int n, m, a[N][N], l[N], c[N];
long long s, mx;

void bk(int k) {
        if (k == n + 1) {
                long long s2 = s;
                for (int j = 1; j <= m; j++) {
                        if (c[j] < 0) {
                                s2 -= c[j];
                                s2 += -c[j];
                        }
                }
                mx = max(mx, s2);
                return;
        }

        for (int i = -1; i <= 1; i += 2) {
                s += i * l[k];
                for (int j = 1; j <= m; j++)
                        c[j] += i * a[k][j];

                bk(k + 1);

                s -= i * l[k];
                for (int j = 1; j <= m; j++)
                        c[j] -= i * a[k][j];
        }
}

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

        bk(1);

        out << mx;
        return 0;
}