제출 #1338952

#제출 시각아이디문제언어결과실행 시간메모리
1338952i_love_spring은행 (IZhO14_bank)C++20
71 / 100
1095 ms16916 KiB
#include <bits/stdc++.h>

using namespace std;

#define ar array
#define ll long long 
const int inf = 2e9;

void solve() {
    int n, m;
    cin >> n >> m;
    vector<int> a(n), b(m);
    for (int i = 0; i < n;i++)
        cin >> a[i];
    
    for (int i = 0; i < m;i++)
        cin >> b[i];
    
    vector<vector<int>> f(n);
    for (int i = 0; i < n;i++) {
        for (int mask = 0; mask < (1 << m);mask++) {
            int sum = 0;
            for (int j = 0; j < m;j++) 
                if (mask >> j & 1) 
                    sum += b[j];
            if (sum == a[i])
                f[i].push_back(mask);    
        }
    }
    vector<vector<int>> dp(n, vector<int> (1 << m, 0));
    for (int x : f[0]) dp[0][x] = 1;
    for (int i = 1; i < n;i++) {
        for (int mask = 0; mask < (1 << m); mask++) {
            for (int x : f[i]) {
                if (!(mask & x)) {
                    dp[i][mask | x] |= dp[i - 1][mask];
                }
            }
        }
    }
    for (int mask = 0; mask < (1 << m);mask++) 
        if (dp[n - 1][mask])
            return (void)(cout << "YES");
    
    cout << "NO";
}

int32_t main() { 

#ifdef Behruz
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif 

    ios :: sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    solve();

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...