제출 #1215409

#제출 시각아이디문제언어결과실행 시간메모리
1215409bbldrizzy은행 (IZhO14_bank)C++20
0 / 100
8 ms840 KiB
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m; cin >> n >> m;
    vector<int> vals(n);
    vector<int> notes(m);
    for (int &u: vals) cin >> u;
    for (int &u: notes) cin >> u;
    vector<vector<int>> sum(1001, vector<int>());
    for (int i = 1; i < (1<<m); i++) {
        vector<int> nds;
        int tmp = i;
        for (int j = 0; j < m; j++) {
            if (tmp&1) nds.push_back(j);
            tmp = tmp >> 1;
        }
        int tsum = 0;
        for (int u: nds) {
            tsum += notes[u];
        }
        sum[tsum].push_back(i);
        // for (int u: nds) {
        //     cout << u << " ";
        // }
        // cout << "\n";
    }
    vector<vector<int>> dp(1<<n);
    for (int i = 0; i < n; i++) {
        dp[1<<i] = sum[vals[i]];
    }
    for (int i = 0; i < (1<<n); i++) {
        vector<int> nds;
        int tmp = i;
        for (int j = 0; j < m; j++) {
            if (tmp&1) nds.push_back(j);
            tmp = tmp >> 1;
        }
        if (nds.size() == 1) continue;
        for (int i = 0; i < nds.size(); i++) {
            vector<int> maskz = dp[1<<nds[i]];
            vector<int> maskz2 = dp[i ^ (1<<nds[i])];
            for (int u: maskz) {
                for (int k: maskz2) {
                    if (u&k == 0) {
                        dp[i].push_back(u||k);
                    }
                }
            }
        }
    }
    if (dp[(1<<n) - 1].size() > 0) {
        cout << "YES";
    } else {
        cout << "NO";
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...