Cod sursa(job #3229026)

Utilizator mirceamaierean41Mircea Maierean mirceamaierean41 Data 13 mai 2024 01:25:12
Problema Zebughil Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.83 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];
// dp[i][j] - capacitatea ramasa folosind i camioane si transportand obiectele aflate in masca j

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; // initital, nu avem nimic in nicio masca

    for (int i = 0; i < n; i++)
        dp[1][(1 << i)] = g - z[i]; // in j avem un singur bit egal cu 1, in camionul 1 ramane diferenta dintre g si z[i]

    for (int mask = 1; mask < m; ++mask)
    {
        for (int i = 1; i <= n; ++i)
            if (dp[i][mask] != -1) // daca cumva avem loc in primele i camioane
            {
                for (int j = 0; j < n; ++j)
                {
                    int maskOfOthers = (1 << j);    // calculam masca ce are setat bitul j pe 1
                    if ((mask & maskOfOthers) == 0) // daca cumva nu exista in masca noastra elementul respectiv
                    {
                        int newMask = mask | maskOfOthers; // calculam noua masca
                        if (z[j] <= dp[i][mask])           // in cazul in care noul obiect incape in primele i camioane, atunci il vom adauga
                            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]); // altfel, aducem un camion nou
                    }
                }
            }
    }

    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;
}