solution-read-file-dynamic-memory.cpp

/* aajjbb */

#include <bits/stdc++.h>

using namespace std;

const int INF = 10010010;
const int MAX_N = 1000;
const int MAX_M = 1000;

int N, M;
int** receita;
bitset<MAX_M>* receita_as_integer;
int** dp;

// Complexidade O(2^N * N^2 * M)
int func(int mask, int now, int best) {
    if (mask == (1 << N) - 1) {
        return best;
    } else {
        int& ans = dp[mask][now];

        if (ans == -1) {
            ans = INF;

            for (int i = 0; i < N; i++) {
                if (!(mask & (1 << i))) {
                    //Proximo valor de toneis em uso.
                    int next_now = now;
                    // Quatidade de valores a serem adicionados aos 'toneis ativos'
                    int to_add = 0;
                    // Quatidade de valores a serem removidos dos 'toneis ativos'
                    int to_remove = 0;

                    //used = mascara com todos os toneis das receitas já usadas
                    //not_used = mascara com todos os toneis das receitas ainda nao usadas
                    bitset<MAX_M> used = 0;
                    bitset<MAX_M> not_used = 0;

                    //Coringas são tintas que são usadas apenas por uma receita, ou seja, não serão incluidas no next_now
                    int jokers = 0;

                    for (int j = 0; j < N; j++) {
                        if (i == j) continue;
                        if (mask & (1 << j)) {
                            used |= receita_as_integer[j];
                        } else {
                            not_used |= receita_as_integer[j];
                        }
                    }

                    for (int j = 0; j < M; j++) {
                        int cntJoker = 0;

                        //Se a mistura i possuir um ingrediente ainda não usado, incrementar to_add
                        if (receita_as_integer[i].test(j) && !used.test(j)) {
                            to_add += 1;

                            cntJoker += 1;
                        }

                        if (receita_as_integer[i].test(j) && !used.test(j)) {
                            //Se a mistura i possuir um elemento que nunca mais sera usado, incrementar to_remove
                            to_remove += 1;

                            cntJoker += 1;
                        }

                        if (cntJoker == 2) {
                            jokers += 1;
                        }
                    }

                    next_now = now + to_add - to_remove;

                    //Maior valor já encontrado de toneis ativos
                    int next_best = max(best, next_now + jokers);

                    ans = min(ans, func(mask | (1 << i), next_now, next_best));
                }
            }
        }

        return ans;
    }
}

int main() {
    string inputfile;
    string outputfile;

    cin >> inputfile;
    cin >> outputfile;

    ifstream istream(inputfile);
    ofstream ostream(outputfile);

    istream >> N >> M;

    if (N > MAX_N || M > MAX_M) {
        ostream << "-1";
    } else {
        dp = new int*[(1 << N)];
        receita = new int*[N];        
        receita_as_integer = new bitset<MAX_M>[N];

        for (int i = 0; i < (1 << N); i++) {
            dp[i] = new int[M];

            for (int j = 0; j < M; j++) {
                dp[i][j] = -1;
            }
        }
        
        for (int i = 0; i < N; i++) {
            receita[i] = new int[M];
            receita_as_integer[i] = 0;

            for (int j = 0; j < M; j++) {
                istream >> receita[i][j];

                if (receita[i][j]) {
                    receita_as_integer[i] |= (1LL << j);
                }
            }
        }

        int ans = func(0, 0, 0);

        ostream << ans << "\n";
    }

    istream.close();
    ostream.close();

    return 0;
}