제출 #1203265

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

bank

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

int N, M, a[20], b[20], total[1<<20], dp[1<<20];

int main() {
    cin >> N >> M;
    for (int i=0; i<N; ++i) cin >> a[i];
    for (int j=0; j<M; ++j) cin >> b[j];

    int FULL = (1<<M);

    // Tính tổng tiền mỗi mask tờ tiền trước
    for (int mask=0; mask<FULL; ++mask) {
        total[mask] = 0;
        for (int j=0; j<M; ++j) 
            if (mask & (1<<j)) total[mask] += b[j];
    }

    fill(dp, dp+FULL, -1);
    dp[0] = 0; // Ban đầu chưa dùng tờ nào, trả được 0 người

    for (int mask=0; mask<FULL; ++mask) {
        if (dp[mask] == -1 || dp[mask] >= N) continue;
        
        // thử chọn thêm tập con submask để trả cho người thứ dp[mask]
        int remain = FULL-1-mask;
        for (int sub = remain; sub; sub = (sub-1)&remain) {
            if (total[sub] == a[dp[mask]]) {
                dp[mask | sub] = max(dp[mask | sub], dp[mask] + 1);
            }
        }
    }

    if (dp[FULL-1] == N) cout << "YES\n";
    else cout << "NO\n";
}

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