제출 #1203265

#제출 시각아이디문제언어결과실행 시간메모리
1203265dungtt은행 (IZhO14_bank)C++20
0 / 100
1 ms328 KiB
#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";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...