Submission #1273240

#TimeUsernameProblemLanguageResultExecution timeMemory
1273240arkanefuryBank (IZhO14_bank)C++20
100 / 100
395 ms47116 KiB
#include <bits/stdc++.h>
#define FOR(x, n, m, d) for(int x = n; x <= m; x += d)
#define nikita ios_base::sync_with_stdio(0), cin.tie(0);
using namespace std;

int n, m, a[21], b[21];
vector<vector<int>> candidates;
unordered_map<int, bool> memo;
bool dfs(int i, int used) {
    if (i == n+1) return 1;
    int key = (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] = 1;
        }
    }
    return memo[key] = 0;
}
signed main() {
  nikita
    cin >> n >> m;
    FOR(i, 1, n, 1) cin >> a[i];
    FOR(i, 1, m, 1) cin >> b[i];
    sort(a+1, a+n+1);
    reverse(a+1, a+n+1);
    vector<int> subsetSum(1 << m, 0);
    FOR(mask, 1, (1 << m) - 1, 1){
        int j = __builtin_ctz(mask);
        subsetSum[mask] = subsetSum[mask ^ (1 << j)] + b[j+1];
    }
    candidates.resize(n+1);
    FOR(i, 1, n, 1){
        FOR(mask, 1, (1 << m) - 1, 1){
            if (subsetSum[mask] == a[i]) {
                candidates[i].push_back(mask);
            }
        }
        if (candidates[i].empty()) {
            cout << "NO\n";
            return 0;
        }
    }
    cout << (dfs(1, 0) ? "YES\n" : "NO\n");
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...