제출 #1181979

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1181979		FaresSTH	은행 (IZhO14_bank)	C++20	71 / 100	1095 ms	3112 KiB

bank

#include "bits/stdc++.h"
using namespace std;

int n, m, a[25], b[25], f[1001], cur[1001];
vector<pair<int, int>> s;
unordered_map<int, bool> memo; // To store memoized results

bool sol(int i, int used) {
    if (i == n) {
        // Check if all required values are satisfied
        for (int j = 0; j < n; j++) {
            if (cur[a[j]] < f[a[j]]) return false;
        }
        return true; // Solution found
    }
    
    // Memoization: Check if this state has already been computed
    int memo_key = (i << 20) | used; // Unique key for memoization
    if (memo.find(memo_key) != memo.end()) {
        return memo[memo_key];
    }
    
    // Try each subset, but prune earlier if no solution can be reached
    for (auto [sum, mask] : s) {
        // If this subset is not used and sum can be incremented
        if ((used & mask) == 0 && cur[sum] < f[sum]) {
            cur[sum]++;
            if (sol(i + 1, used | mask)) {
                return memo[memo_key] = true; // Cache result
            }
            cur[sum]--; // Backtrack
        }
    }
    
    return memo[memo_key] = false; // Cache result
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);

    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        f[a[i]]++;
    }

    for (int i = 0; i < m; i++) cin >> b[i];

    // Generate all possible sums and their corresponding bitmasks
    for (int mask = 0; mask < (1 << m); mask++) {
        int sum = 0;
        for (int j = 0; j < m; j++) {
            if (mask & (1 << j)) sum += b[j];
        }
        if (f[sum]) s.emplace_back(sum, mask);
    }

    // Sort subsets by sum size for better greedy decisions
    sort(s.begin(), s.end(), [](const pair<int, int>& lhs, const pair<int, int>& rhs) {
        return lhs.first > rhs.first; // Prefer larger sums first
    });

    // Call the recursive function starting from index 0 and no subsets used
    if (sol(0, 0)) {
        cout << "YES";
    } else {
        cout << "NO";
    }

    return 0;
}

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