Submission #1338953

#TimeUsernameProblemLanguageResultExecution timeMemory
1338953i_love_springBank (IZhO14_bank)C++20
71 / 100
1096 ms16900 KiB
#include <bits/stdc++.h>

using namespace std;

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

void solve() {
    int n, m;
    cin >> n >> m;
    vector<int> a, b, cnt(N, 0);
    for (int x, i = 0; i < n;i++)
        cin >> x, cnt[x]++;
    
    for (int x, i = 0; i < m;i++) {
        cin >> x;
        if (cnt[x] > 0) 
            cnt[x]--;
        else 
            b.push_back(x);
    }

    for (int i = 1; i < N;i++) 
        for (int j = 0; j < cnt[i];j++) 
            a.push_back(i);

    n = a.size();
    m = b.size();

    if (n * 2 > m)  
        return (void)(cout << "NO");

    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...