제출 #1159029

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1159029		ryaminty	은행 (IZhO14_bank)	C++17	46 / 100	175 ms	1460 KiB

bank

#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";
}

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