Submission #1203272

#	Time	Username	Problem	Language	Result	Execution time	Memory
1203272		dungtt	Bank (IZhO14_bank)	C++20	71 / 100	1095 ms	436 KiB

bank

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

int N, M;
vector<int> salaries, banknotes;
vector<bool> used;

bool tryPay(int person) {
    if (person == N) 
        return true;  // Đã trả đủ tiền cho tất cả mọi người

    // Dùng bitmask để thử chọn tờ tiền nào cho người thứ person
    int totalCombinations = 1 << M;
    for (int mask = 1; mask < totalCombinations; mask++) {
        int sum = 0;
        bool ok = true;

        // Kiểm tra tờ tiền trong mask có thể sử dụng không
        for (int i = 0; i < M; i++) {
            if (mask & (1 << i)) {
                if (used[i]) {
                    ok = false; 
                    break;
                }
                sum += banknotes[i];
            }
        }

        // Nếu hợp lệ, đúng bằng lương người hiện tại
        if (ok && sum == salaries[person]) {
            // Đánh dấu các tờ tiền này là đã dùng
            for (int i = 0; i < M; i++)
                if (mask & (1 << i))
                    used[i] = true;

            // Thử trả cho người tiếp theo
            if (tryPay(person + 1))
                return true;

            // Quay lui (huỷ đánh dấu)
            for (int i = 0; i < M; i++)
                if (mask & (1 << i))
                    used[i] = false;
        }
    }

    return false;  // Không tìm được cách trả hợp lệ
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> N >> M;
    salaries.resize(N);
    banknotes.resize(M);
    used.assign(M, false);

    for (int &x : salaries) cin >> x;
    for (int &x : banknotes) cin >> x;

    if (tryPay(0))
        cout << "YES";
    else
        cout << "NO";

    return 0;
}

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