Cod sursa(job #3229039)

Utilizator andrei.nNemtisor Andrei andrei.n Data 13 mai 2024 12:12:01
Problema Zebughil Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1 kb
#include <iostream>
#include <vector>
#include <cassert>
#include <algorithm>

typedef long long ll;

int main() {
    freopen("zebughil.in", "r", stdin);
    freopen("zebughil.out", "w", stdout);

    int n, g;
    while (std::cin >> n) {
        std::cin >> g;
        int a[n] = {};
        for (auto &x : a) {
            std::cin >> x;
        }

        int dp[1 << n];
        dp[0] = 1;
        for (int mask = 1; mask < (1 << n); mask++) {
            ll sum = 0;
            for (int i = 0; i < n; i++) {
                if ((mask >> i) & 1) {
                    sum += a[i];
                }
            }
            dp[mask] = 1e9;
            if (sum <= g) {
                dp[mask] = 1;
            }
            for (int submask = mask; submask != 0; submask = (submask - 1) & mask) {
                dp[mask] = std::min(dp[mask], dp[submask] + dp[mask ^ submask]);
            }
        }

       std::cout << dp[(1 << n) - 1] << '\n';
    }

    return 0;
}