제출 #1370148

#제출 시각아이디문제언어결과실행 시간메모리
1370148LOLOLO은행 (IZhO14_bank)C++17
100 / 100
93 ms21972 KiB
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;

int n, m;
int a[21], b[21];
vector<int> valid_masks[21];
// memo[người][trạng thái tiền] -> -1: chưa biết, 0: sai, 1: đúng
signed char memo[21][1 << 20];

bool solve(int idx, int mask) {
    // Nếu đã trả lương xong cho tất cả n người
    if (idx == n) return 1;

    // Kiểm tra bộ nhớ đệm
    if (memo[idx][mask] != -1) return memo[idx][mask];

    // Thử tất cả các tổ hợp tiền hợp lệ cho người này
    for (int sub : valid_masks[idx]) {
        // Kiểm tra xem tập tiền 'sub' có phải là tập con của 'mask' hiện tại không
        if ((sub & mask) == sub) {
            // Nếu dùng tập 'sub', tiền còn lại là (mask ^ sub)
            if (solve(idx + 1, mask ^ sub)) {
                return memo[idx][mask] = 1;
            }
        }
    }

    return memo[idx][mask] = 0;
}

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

    if (!(cin >> n >> m)) return 0;

    long long sum_a = 0, sum_b = 0;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        sum_a += a[i];
    }
    for (int i = 0; i < m; i++) {
        cin >> b[i];
        sum_b += b[i];
    }

    // Điều kiện cần cơ bản
    if (sum_a > sum_b) {
        cout << "NO";
        return 0;
    }

    // Sắp xếp lương giảm dần để tối ưu hóa việc tìm kiếm (Pruning)
    sort(a, a + n, greater<int>());

    // Tiền xử lý: Tìm mọi mask có tổng bằng từng mức lương a[i]
    for (int mask = 1; mask < (1 << m); mask++) {
        long long current_sum = 0;
        for (int i = 0; i < m; i++) {
            if ((mask >> i) & 1) {
                current_sum += b[i];
            }
        }
        for (int i = 0; i < n; i++) {
            if (current_sum == a[i]) {
                valid_masks[i].push_back(mask);
            }
        }
    }

    // Khởi tạo bộ nhớ đệm với giá trị -1
    memset(memo, -1, sizeof(memo));

    // Bắt đầu từ người thứ 0 với đầy đủ m tờ tiền (tất cả các bit là 1)
    if (solve(0, (1 << m) - 1)) {
        cout << "YES";
    } else {
        cout << "NO";
    }

    return 0;
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…