제출 #1168613

#제출 시각아이디문제언어결과실행 시간메모리
1168613GoBananas69Bank (IZhO14_bank)C++20
19 / 100
65 ms4540 KiB
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <bitset>
typedef long long ll;
using namespace std;

int n, m;

void solve(int i, vector<vector<int>> &match, vector<int> curr) {
    if (i == n) {
        bool ok = true;
        for (int i = 0; i < n && ok; ++i) {
            for (int j = i + 1; j < n && ok; ++j) {
                if (curr[i] & curr[j]) {
                    ok = false;
                }
            }
        }
        if (ok) {
            cout << "YES\n";
            exit(0);
        }
    }
    for (int &j: match[i]) {        
        curr[i] = j;
        solve(i + 1, match, curr);
    }
}

signed main() {
    cin.tie() -> sync_with_stdio(0);
    cin >> n >> m;
    vector<int> a(n), b(m);
    for (int &i: a) cin >> i;
    for (int &i: b) cin >> i;
    vector<int> mask;
    vector<vector<int>> match(n);
    for (int i = 0; i<(1 << m); ++i) {
        int curr = 0;
        for (int j = 0; j<m; ++j) {
            if (i & (1 << j)) curr += b[j];
        }
        for (int j = 0; j<n; ++j) {
            if (curr == a[j]) match[j].push_back(i);
        }
        mask.push_back(curr);
    }
    for (auto &v: match) {
        if (v.empty()) {
            cout << "NO\n";
            return 0;
        }
    }
    vector<int> curr(n);
    solve(0, match, curr);
    cout << "NO\n";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...