제출 #1303781

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1303781		vladneagu	은행 (IZhO14_bank)	C++20	0 / 100	2 ms	972 KiB

bank

#include <bits/stdc++.h>
using namespace std;
int N, M;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    if(!(cin >> N >> M)) return 0;
    vector<int> a(N);
    for(int i=0;i<N;i++) cin >> a[i];
    vector<int> b(M);
    for(int j=0;j<M;j++) cin >> b[j];

    long long sumA = 0, sumB = 0;
    for(int x: a) sumA += x;
    for(int x: b) sumB += x;
    if(sumA != sumB){
        cout << "NO\n";
        return 0;
    }

    // precompute sum for every mask
    int S = 1<<M;
    vector<int> sum(S,0);
    for(int mask=1; mask<S; ++mask){
        int lb = mask & -mask;
        int pos = __builtin_ctz(lb);
        sum[mask] = sum[mask ^ lb] + b[pos];
    }

    // map from salary value -> masks that sum to it
    unordered_map<int, vector<int>> masksFor;
    for(int mask=0; mask<S; ++mask){
        masksFor[ sum[mask] ].push_back(mask);
    }

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

    // quick check: any salary value without any matching mask -> NO
    for(int i=0;i<N;i++){
        if(masksFor.find(a[i]) == masksFor.end() || masksFor[a[i]].empty()){
            cout << "NO\n";
            return 0;
        }
    }

    vector<char> bad(S, 0); // bad[used_mask] == true => already explored and impossible
    function<bool(int,int)> dfs = [&](int cur, int used)->bool{
        if(cur == N) return true;
        if(bad[used]) return false;
        auto &vec = masksFor[a[cur]];
        for(int mask : vec){
            if( (mask & used) == 0 ){
                if(dfs(cur+1, used | mask)) return true;
            }
        }
        bad[used] = 1;
        return false;
    };

    bool ok = dfs(0, 0);
    cout << (ok ? "YES\n" : "NO\n");
    return 0;
}

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