Submission #1273239

#	Time	Username	Problem	Language	Result	Execution time	Memory
1273239		arkanefury	Bank (IZhO14_bank)	C++20	71 / 100	1098 ms	35828 KiB

bank

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

const int N = 21;
int n, m, a[N], b[N];
vector<vector<int>> candidates;
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");
}

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