solution-read-file.cpp

/* aajjbb */

#include <bits/stdc++.h>

using namespace std;

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

int N, M;
int receita[MAX_N][MAX_M];
bitset<MAX_M> receita_as_integer[MAX_N];
int dp[1 << (MAX_N)][MAX_M];

// 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 {
        for (int i = 0; i < N; i++) {
            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);
                }
            }
        }

        memset(dp, -1, sizeof(dp));

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

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

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

    return 0;
}