Cod sursa(job #2085259)

Utilizator himamisBencze Balazs himamis Data 9 decembrie 2017 21:11:28
Problema Jocul Flip Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.44 kb
#include <iostream>
#include <fstream>
#include <climits>
#include <cmath>

using namespace std;
int n, m;
int *mat;
int *rows;
int *cols;
bool stop = false;

int mm = -1;

void nullify() {
    for (int i = 0; i < n; i++) {
        rows[i] = 1;
    }
    for (int i = 0; i < m; i++) {
        cols[i] = 1;
    }
}

void be() {
    ifstream f("flip.in");
    f >> n >> m;
    mat = new int[n * m];
    for (int i = 0; i < n * m; i++) {
        f >> mat[i];
    }
    rows = new int[n];
    cols = new int[m];
    f.close();
}

int tot() {
    int tot = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            tot += mat[i * m + j] * rows[i] * cols[j];
        }
    }
    return tot;
}

bool inc(int *v, int n) {
    int index = 0;
    while (v[index] == -1 && index < n) {
        v[index] = 1;
        index++;
    }
    if (index < n) {
        v[index] = -1;
    }
    return index >= n;
}

void bt() {
    if (!stop) {
        for (int i = 0; i < n; i++) {
            int sum = 0;
            for (int j = 0; j < m; j++) {
                sum += mat[i * m + j] * cols[j];
            }
            rows[i] = (sum < 0) ? -1 : 1;
        }
        int val = tot();
        if (val > mm) {
            mm = val;
        }
        stop = inc(cols, m);
        bt();
    }
}

void megold() {
    nullify();
    bt();
}

void ki() {
    ofstream g("flip.out");
    g << mm;
    g.close();
}

int main() {
    be();
    megold();
    ki();
}