제출 #1200544

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1200544		PlayVoltz	Bank (IZhO14_bank)	C++20	100 / 100	607 ms	12700 KiB

bank

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
using namespace std;

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

    int n, m;
    if (!(cin >> n >> m)) return 0;

    vector<int> ppl(n), notes(m);
    unordered_set<int> exist;          // fast membership test for sums
    for (int &x : ppl) {
        cin >> x;
        exist.insert(x);
    }
    for (int &x : notes) cin >> x;

    /* Pre-compute, for every person-sum that appears, all note-subsets
       (bitmasks) whose total equals that sum. */
    unordered_map<int, vector<int>> masks;
    for (int mask = 0; mask < (1 << m); ++mask) {
        int sum = 0;
        for (int j = 0; j < m; ++j)              // NOTE: j < m, not <= m
            if (mask & (1 << j)) sum += notes[j];
        if (exist.count(sum)) masks[sum].push_back(mask);
    }

    /* DP: cur = every global-mask reachable after processing idx-1 people.
       Start with 0 (nothing used). */
    unordered_set<int> cur{0};

    for (int idx = 0; idx < n && !cur.empty(); ++idx) {
        unordered_set<int> nxt;
        const auto &choices = masks[ppl[idx]];   // all subsets matching this person
        for (int used : cur) {
            for (int take : choices)
                if ((used & take) == 0)          // disjoint ⇒ can assign
                    nxt.insert(used | take);
        }
        cur.swap(nxt);                           // move to next person
    }

    cout << (cur.empty() ? "NO" : "YES");
    return 0;
}

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