Cod sursa(job #3229025)

Utilizator mirceamaierean41Mircea Maierean mirceamaierean41 Data 13 mai 2024 00:57:01
Problema Zebughil Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.31 kb
#include <fstream>

using namespace std;

ifstream fin("zebughil.in");
ofstream fout("zebughil.out");

const int NMAX = 1 << 18;

int dp[18][NMAX], z[18];

int solve()
{
    int n, g;
    fin >> n >> g;

    for (int i = 0; i < n; ++i)
        fin >> z[i];

    int m = (1 << n);

    for (int mask = 0; mask < m; ++mask)
        for (int i = 1; i <= n; ++i)
            dp[i][mask] = -1;

    for (int i = 0; i < n; i++)
        dp[1][(1 << i)] = g - z[i];

    for (int mask = 1; mask < m; ++mask)
    {
        for (int i = 1; i <= n; ++i)
            if (dp[i][mask] != -1)
            {
                for (int j = 0; j < n; ++j)
                {
                    int maskOfOthers = (1 << j);
                    if ((mask & maskOfOthers) == 0)
                    {
                        int newMask = mask | maskOfOthers;
                        if (z[j] <= dp[i][mask])
                            dp[i][newMask] = max(dp[i][newMask], dp[i][mask] - z[j]);
                        else
                            dp[i + 1][newMask] = max(dp[i + 1][newMask], g - z[j]);
                    }
                }
            }
    }

    for (int i = 1; i <= n; ++i)
        if (dp[i][m - 1] != -1)
            return i;

    return 0;
}

int main()
{
    for (int i = 0; i < 3; ++i)
        fout << solve() << '\n';
    return 0;
}