제출 #1178690

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1178690		GoBananas69	은행 (IZhO14_bank)	C++20	46 / 100	1 ms	328 KiB

bank

#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;
}

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