제출 #1273236

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1273236		arkanefury	Bank (IZhO14_bank)	C++20	100 / 100	382 ms	47080 KiB

bank

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

int N, M;
vector<int> a, b;
vector<vector<int>> candidates;
unordered_map<int, bool> memo;

bool dfs(int i, int used) {
    if (i == (int)a.size()) return true;
    long long key = ((long long)i << 20) | used; 
    if (memo.count(key)) return memo[key];

    for (int mask : candidates[i]) {
        if ((used & mask) == 0) {
            if (dfs(i + 1, used | mask))
                return memo[key] = true;
        }
    }
    return memo[key] = false;
}

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

    cin >> N >> M;
    a.resize(N);
    b.resize(M);

    for (int i = 0; i < N; i++) cin >> a[i];
    for (int j = 0; j < M; j++) cin >> b[j];

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

    vector<int> subsetSum(1 << M, 0);
    for (int mask = 1; mask < (1 << M); mask++) {
        int j = __builtin_ctz(mask);
        subsetSum[mask] = subsetSum[mask ^ (1 << j)] + b[j];
    }
    candidates.resize(N);
    for (int i = 0; i < N; i++) {
        for (int mask = 1; mask < (1 << M); mask++) {
            if (subsetSum[mask] == a[i]) {
                candidates[i].push_back(mask);
            }
        }
        if (candidates[i].empty()) {
            cout << "NO\n";
            return 0;
        }
    }

    cout << (dfs(0, 0) ? "YES\n" : "NO\n");
    return 0;
}

• Subtask 1: 19 / 19
• Subtask 2: 25 / 25
• Subtask 3: 27 / 27
• Subtask 4: 29 / 29