Submission #1232383

#	Time	Username	Problem	Language	Result	Execution time	Memory
1232383		ishaanthenerd	은행 (IZhO14_bank)	C++20	19 / 100	66 ms	78408 KiB

bank

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 1e9 + 7;

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

    int n, m;
    cin >> n >> m;
    vector<int> a(n), b(m);
    for (int i = 0; i < n; i++) cin >> a.at(i);
    for (int i = 0; i < m; i++) cin >> b.at(i);

    vector<int> sum((1 << m), 0);
    for (int mask = 1; mask < (1 << m); mask++) {
        int index = -1;
        for (int i = 0; i < m; i++) {
            if (mask & (1 << i)) {
                index = i;
                break;
            }
        }
        sum.at(mask) = sum.at(mask ^ (1 << index)) + b.at(index);
    }

    int previous_or_all = 0;
    int current_or_all = 0;
    vector<vector<bool>> dp((1 << m), vector<bool>(n, 0));
    for (int i = 0; i < n; i++) {
        // find all previous ones that work (mask1)
        // find all current ones that work (mask2)
        // if mask1 & mask2 = 0, then dp.at(mask2).at(i) = true
        // else, mask1 & mask2 != 0 for all mask1, so or_all(mask1) & mask2 != 0
        
        for (int mask = 1; mask < (1 << m); mask++) {
            if (sum.at(mask) != a.at(i)) continue;
            if ((previous_or_all & mask) != 0) continue;
            dp.at(mask).at(i) = true;
            current_or_all |= mask;
        }
        previous_or_all = current_or_all;
        current_or_all = 0;
    }

    bool ans = false;
    for (int mask = 1; mask < (1 << m); mask++) {
        if (dp.at(mask).back()) {
            ans = true;
            break;
        }
    }
    cout << (ans ? "YES" : "NO") << endl;

    return 0;
}

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