제출 #1369190

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1369190		haught_veath	은행 (IZhO14_bank)	C++20	100 / 100	284 ms	129112 KiB

bank

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    cin >> N >> M;

    vector<int> a(N), b(M);

    for (int &x : a) cin >> x;
    for (int &x : b) cin >> x;

    sort(a.rbegin(), a.rend());

    int FULL = 1 << M;

    vector<int> sum(FULL, 0);

    for (int mask = 1; mask < FULL; mask++) {
        int bit = __builtin_ctz(mask);
        sum[mask] = sum[mask ^ (1 << bit)] + b[bit];
    }

    // good[i] = all subsets whose sum = a[i]
    vector<vector<int>> good(N);

    for (int mask = 1; mask < FULL; mask++) {
        for (int i = 0; i < N; i++) {
            if (sum[mask] == a[i]) {
                good[i].push_back(mask);
            }
        }
    }

    queue<pair<int,int>> q;
    // (used_mask, satisfied_customers)

    vector<vector<int>> vis(FULL, vector<int>(N + 1, 0));

    q.push({0, 0});
    vis[0][0] = 1;

    while (!q.empty()) {
        auto [mask, id] = q.front();
        q.pop();

        if (id == N) {
            cout << "YES\n";
            return 0;
        }

        for (int sub : good[id]) {
            if (mask & sub) continue;

            int nmask = mask | sub;

            if (!vis[nmask][id + 1]) {
                vis[nmask][id + 1] = 1;
                q.push({nmask, id + 1});
            }
        }
    }

    cout << "NO\n";
}

• 서브태스크 1: 19 / 19
• 서브태스크 2: 25 / 25
• 서브태스크 3: 27 / 27
• 서브태스크 4: 29 / 29