제출 #1203301

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1203301		dungtt	은행 (IZhO14_bank)	C++20	100 / 100	82 ms	8520 KiB

bank

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int num_people, num_notes;
    cin >> num_people >> num_notes;

    vector<int> salaries(num_people);       // Tiền lương từng người
    vector<int> banknotes(num_notes);       // Mệnh giá từng tờ tiền

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

    int total_states = 1 << num_notes;      // Số tập con của banknotes

    // dp[state]: số người đã được trả lương nếu dùng các tờ tiền trong 'state'
    vector<int> people_paid(total_states, -1);
    // leftover[state]: số tiền đã cộng dồn cho người hiện tại ở trạng thái 'state'
    vector<int> current_sum(total_states, -1);

    // Trạng thái khởi đầu: chưa dùng tờ nào, chưa trả ai, dư 0 tiền
    people_paid[0] = 0;
    current_sum[0] = 0;

    for (int state = 0; state < total_states; ++state) {
        // Nếu trạng thái không hợp lệ, bỏ qua
        if (people_paid[state] == -1) continue;

        // Thử thêm từng tờ tiền chưa có trong state
        for (int i = 0; i < num_notes; ++i) {
            if (state & (1 << i)) continue; // tờ tiền thứ i đã dùng rồi

            int next_state = state | (1 << i);
            int person = people_paid[state]; // đang trả cho người thứ mấy
            if (person >= num_people) continue;

            int sum = current_sum[state] + banknotes[i]; // cộng thêm tiền tờ mới
            int target = salaries[person];               // tiền lương người hiện tại

            if (sum < target) {
                // chưa đủ, tiếp tục trả người này
                people_paid[next_state] = person;
                current_sum[next_state] = sum;
            } else if (sum == target) {
                // vừa đủ, chuyển sang người tiếp theo
                people_paid[next_state] = person + 1;
                current_sum[next_state] = 0;
            }
        }

        // Nếu đã trả hết mọi người → thành công
        if (people_paid[state] == num_people) {
            cout << "YES\n";
            return 0;
        }
    }

    // Nếu duyệt hết không tìm được cách chia hợp lệ
    cout << "NO\n";
    return 0;
}

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