제출 #1277183

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1277183		souvenir_vayne	은행 (IZhO14_bank)	C++20	100 / 100	273 ms	8816 KiB

bank

#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> a(N), b(M);
    long long sumA = 0, sumB = 0;
    for (int i = 0; i < N; ++i) { cin >> a[i]; sumA += a[i]; }
    for (int j = 0; j < M; ++j) { cin >> b[j]; sumB += b[j]; }

    // Quick rejects
    if (sumB < sumA) { cout << "NO\n"; return 0; }
    if (M < N) { cout << "NO\n"; return 0; }

    // Sort salaries descending (helps pruning)
    sort(a.rbegin(), a.rend());

    int FULL = 1 << M;
    vector<int> sumMask(FULL, 0);
    for (int mask = 1; mask < FULL; ++mask) {
        int lsb = __builtin_ctz(mask);
        int prev = mask & (mask - 1);
        sumMask[mask] = sumMask[prev] + b[lsb];
    }

    // Map salary value -> list of indices in sorted a[] that have that value
    unordered_map<int, vector<int>> who;
    who.reserve(N * 2);
    for (int i = 0; i < N; ++i) who[a[i]].push_back(i);

    // subsets_for_person[k] = list of banknote-masks that exactly sum to a[k]
    vector<vector<int>> subsets_for_person(N);
    for (int mask = 1; mask < FULL; ++mask) {
        auto it = who.find(sumMask[mask]);
        if (it != who.end()) {
            // add this mask to all persons that want this sum (could be multiple people with same salary)
            for (int idx : it->second) subsets_for_person[idx].push_back(mask);
        }
    }

    // DP over banknote masks: dp[mask] = how many people (prefix of sorted a) can be paid using mask
    vector<int> dp(FULL, -1);
    dp[0] = 0;

    for (int mask = 0; mask < FULL; ++mask) {
        int k = dp[mask];
        if (k < 0) continue;
        if (k == N) { cout << "YES\n"; return 0; } // already paid all
        // try all subsets that pay person k
        for (int sub : subsets_for_person[k]) {
            if ((mask & sub) == 0) {
                int nmask = mask | sub;
                if (dp[nmask] < k + 1) dp[nmask] = k + 1;
            }
        }
    }

    // check if any mask reached dp == N
    for (int mask = 0; mask < FULL; ++mask) if (dp[mask] == N) { cout << "YES\n"; return 0; }
    cout << "NO\n";
    return 0;
}

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