Submission #1308577

#TimeUsernameProblemLanguageResultExecution timeMemory
1308577buzdiBank (IZhO14_bank)C++17
52 / 100
1095 ms4200 KiB
#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int NMAX = 20;
const int VMAX = 1000;

int n, m, maxi;
int a[NMAX + 1], b[NMAX + 1];
vector<int> v[VMAX + 1];
bool dp[NMAX + 1][1 << NMAX];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

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

    maxi = *max_element(a + 1, a + n + 1);
    for(int mask = 1; mask < (1 << m); mask++) {
        int sum = 0;
        for(int i = 1; i <= m; i++) {
            if(mask >> (i - 1) & 1) {
                sum += b[i];
            }
        }
        if(sum <= maxi) {
            v[sum].push_back(mask);
        }
    }

    dp[0][(1 << m) - 1] = 1;
    for(int i = 1; i <= n; i++) {
        for(int x : v[a[i]]) {
            for(int mask = 0; mask < (1 << m); mask++) {
                if(!(mask & x)) {
                    dp[i][mask] |= dp[i - 1][mask ^ x];
                }
            }
        }
    }
    for(int mask = 0; mask < (1 << m); mask++) {
        if(dp[n][mask]) {
            cout << "YES\n";
            return 0;
        }
    }
    cout << "NO\n";
    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...