제출 #1159029

#제출 시각아이디문제언어결과실행 시간메모리
1159029ryaminty은행 (IZhO14_bank)C++17
46 / 100
175 ms1460 KiB
#include <bits/stdc++.h>
using namespace std;

constexpr int mxN = 20, mxSum = 1000;
int n, m;
int a[mxN], b[mxN];
bool dp[1<<20];

int main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n >> m;

    for (int i=0; i<n; ++i) 
        cin >> a[i];
    
    for (int i=0; i<m; ++i) 
        cin >> b[i];

    dp[0] = true; // Base case: Empty set can form sum 0
    for (int mask=0; mask < (1<<m); ++mask){
        if (!dp[mask]) continue;
        int sum = 0;
        for (int i=0; i<m; ++i)
            if (mask & (1<<i)) sum += b[i];

        for (int i=0; i<m; ++i){
            if (!(mask & (1<<i)) && sum + b[i] <= mxSum)
                dp[mask | (1<<i)] = true;
        }
    }

    // Check if we can form each salary exactly
    for (int i=0; i<n; ++i){
        bool canPay = false;
        for (int mask=0; mask < (1<<m); ++mask){
            int sum = 0;
            for (int j=0; j<m; ++j)
                if (mask & (1<<j)) sum += b[j];

            if (sum == a[i]){
                canPay = true;
                break;
            }
        }
        if (!canPay){
            cout << "NO\n";
            return 0;
        }
    }
    cout << "YES\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...