Submission #1292931

#	Time	Username	Problem	Language	Result	Execution time	Memory
1292931		dm10r7	은행 (IZhO14_bank)	C++20	100 / 100	263 ms	6720 KiB

bank

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

int a[21], b[21];
vector<int> cand[21];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, m;
    cin >> n >> m;
    for(int i = 0; i < n; i++) cin >> a[i];
    for(int i = 0; i < m; i++) cin >> b[i];
    sort(a, a + n, greater<int>());
    int tot = 1 << m;
    vector<int> subsum(tot, 0);
    for(int mask = 1; mask < tot; mask++) {
        int bit = __builtin_ctz(mask);
        subsum[mask] = subsum[mask ^ (1 << bit)] + b[bit];
    }
    for(int i = 0; i < n; i++) {
        for(int mask = 0; mask < tot; mask++) {
            if(subsum[mask] == a[i]) cand[i].push_back(mask);
        }
    }
    vector<char> dp(tot, 0);
    vector<char> ndp(tot, 0);
    dp[0] = 1;
    for(int i = 0; i < n; i++) {
        fill(ndp.begin(), ndp.end(), 0);
        for(int mask = 0; mask < tot; mask++) {
            if(dp[mask]) {
                for(int sub : cand[i]) {
                    if((mask & sub) == 0) {
                        ndp[mask | sub] = 1;
                    }
                }
            }
        }
        dp.swap(ndp);
    }
    bool ok = false;
    for(int mask = 0; mask < tot; mask++) {
        if(dp[mask]) {
            ok = true;
            break;
        }
    }
    puts(ok ? "YES" : "NO");
    return 0;
}

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