제출 #1141295

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1141295		Bilal_Coder	은행 (IZhO14_bank)	C++20	19 / 100	193 ms	412 KiB

bank

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

bool canPayAllSalaries(vector<int>& salaries, vector<int>& banknotes) {
    int n = salaries.size();
    int m = banknotes.size();

    // Iterate over each salary
    for (int salary : salaries) {
        // DP array to track valid masks for the current salary
        vector<bool> dp(1 << m, false);
        dp[0] = true; // Base case: no banknotes used sums to 0.

        // Process subsets of banknotes
        for (int mask = 0; mask < (1 << m); ++mask) {
            if (!dp[mask]) continue;

            int current_sum = 0;
            for (int j = 0; j < m; ++j) {
                if (mask & (1 << j)) current_sum += banknotes[j];
            }

            // Try adding each unused banknote
            for (int j = 0; j < m; ++j) {
                if (!(mask & (1 << j)) && current_sum + banknotes[j] <= salary) {
                    dp[mask | (1 << j)] = true;
                }
            }
        }

        // Check if we can achieve the current salary
        bool canPay = false;
        for (int mask = 0; mask < (1 << m); ++mask) {
            int sum = 0;
            for (int j = 0; j < m; ++j) {
                if (mask & (1 << j)) sum += banknotes[j];
            }
            if (sum == salary) {
                canPay = true;

                // Remove used banknotes
                vector<int> new_banknotes;
                for (int j = 0; j < m; ++j) {
                    if (!(mask & (1 << j))) new_banknotes.push_back(banknotes[j]);
                }
                banknotes = new_banknotes;
                m = banknotes.size();
                break;
            }
        }

        if (!canPay) return false;
    }

    return true;
}

int main() {
    int n, m;
    cin >> n >> m;

    vector<int> salaries(n), banknotes(m);
    for (int i = 0; i < n; ++i) cin >> salaries[i];
    for (int i = 0; i < m; ++i) cin >> banknotes[i];

    if (canPayAllSalaries(salaries, banknotes)) {
        cout << "YES" << endl;
    } else {
        cout << "NO" << endl;
    }

    return 0;
}

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