Cod sursa(job #2323875)

Utilizator BogdanVMVilculescu Mihai Bogdan BogdanVM Data 19 ianuarie 2019 21:42:35
Problema Jocul Flip Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.56 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, const std::vector<bool>& flip) {
    int totalSum = 0;
    for (int i = 0; i < table[0].size(); ++i) {
        int s = 0;
        for (int j = 0; j < table.size(); ++j) {
            if (flip[j]) {
                s += (-table[j][i]);
            } else {
                s += table[j][i];
            }
        }

        totalSum += abs(s);
    }

    return totalSum;
}

void backtracking(int k, const Matrix& table, std::vector<int>& nextStep, std::vector<bool>& flip, int& totalSum) {
    int n = table.size();
    for (int i = nextStep[k]; i < n; ++i) {
        nextStep[k+1] = i + 1;
        flip[i] = true;

        int s = getSum(table, flip);
        if (s > totalSum) {
            totalSum = s;
        }

        backtracking(k + 1, table, nextStep, flip, totalSum);
        flip[i] = false;
    }
}

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

    read("flip.in", table, n, m);

    std::vector<int> nextStep(n+1, 0);
    std::vector<bool> flip(n, false);
    int totalSum = 0;

    backtracking(0, table, nextStep, flip, totalSum);

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

    return 0;
}