Submission #1178690

#TimeUsernameProblemLanguageResultExecution timeMemory
1178690GoBananas69Bank (IZhO14_bank)C++20
46 / 100
1 ms328 KiB
#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>

using namespace std;

vector<int> generate_subset_sums(const vector<int>& nums) {
    vector<int> sums;
    int n = nums.size();
    for (int mask = 0; mask < (1 << n); ++mask) {
        int sum = 0;
        for (int i = 0; i < n; ++i) {
            if (mask & (1 << i)) sum += nums[i];
        }
        sums.push_back(sum);
    }
    return sums;
}

bool solve_mitm(const vector<int>& a, const vector<int>& b) {
    int m = b.size();
    int half = m / 2;
    vector<int> left(b.begin(), b.begin() + half);
    vector<int> right(b.begin() + half, b.end());

    vector<int> left_sums = generate_subset_sums(left);
    vector<int> right_sums = generate_subset_sums(right);

    sort(right_sums.begin(), right_sums.end());

    for (int target : a) {
        bool found = false;
        for (int sum_left : left_sums) {
            int needed = target - sum_left;
            if (binary_search(right_sums.begin(), right_sums.end(), needed)) {
                found = true;
                break;
            }
        }
        if (!found) return false;
    }
    return true;
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> a(n), b(m);
    for (int &x : a) cin >> x;
    for (int &x : b) cin >> x;

    if (solve_mitm(a, b)) cout << "YES\n";
    else cout << "NO\n";

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...