Cod sursa(job #2323874)

Utilizator BogdanVMVilculescu Mihai Bogdan BogdanVM Data 19 ianuarie 2019 21:41:09
Problema Jocul Flip Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.32 kb
#include <fstream>
#include <vector>
#include <math.h>

typedef std::vector<std::vector<int> > Matrix;

void read(const char* fileName, Matrix& table, int& n, int& m) {
    std::ifstream fin(fileName);

    fin >> n >> m;
    table.resize(n);
    for (int i = 0; i < n; ++i) {
        table[i].resize(m);
        for (int j = 0; j < m; ++j) {
            fin >> table[i][j];
        }
    }

    fin.close();
}

int getSum(const Matrix& table, int k) {
    int totalSum = 0;
    for (int i = 0; i < table[0].size(); ++i) {
        int s = 0;
        for (int j = 0; j < table.size(); ++j) {
            if (j == k) {
                s += (-table[j][i]);
            } else {
                s += table[j][i];
            }
        }

        totalSum += abs(s);
    }

    return totalSum;
}

void backtracking(int k, const Matrix& table, int& totalSum) {
    int n = table.size();
    if (k == n) {
        return;
    }

    for (int i = k; i < n; ++i) {
        int s = getSum(table, i);
        if (s > totalSum) {
            totalSum = s;
        }

        backtracking(k + 1, table, totalSum);
    }
}

int main()
{
    Matrix table;
    int n, m;

    read("flip.in", table, n, m);
    int totalSum = 0;

    backtracking(0, table, totalSum);

    std::ofstream fout("flip.out");
    fout << totalSum << "\n";
    fout.close();

    return 0;
}