Cod sursa(job #3263059)

Utilizator Mihai_PopescuMihai Popescu Mihai_Popescu Data 13 decembrie 2024 00:40:52
Problema Jocul Flip Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.14 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 uz[20];

long long suma(int n, int m) {
    long long sum = 0;
    for (int i = 1; i <= n; ++i) {
        long long s = 0;
        for (int j = 1; j <= m; ++j) {
            if (uz[j]) {
                s += a[i][j];
            } else {
                s -= a[i][j];
            }
        }

        if (s < 0) {
            s *= -1;
        }
        sum += s;
    }
    return sum;
}

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

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

            back(k + 1, n, m);

            uz[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;
}