Submission #1166301

#TimeUsernameProblemLanguageResultExecution timeMemory
1166301SulABank (IZhO14_bank)C++20
52 / 100
51 ms4424 KiB
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define bitcount __builtin_popcountll
#define all(a) (a).begin(), (a).end()
using namespace std;
using namespace __gnu_pbds;
template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

bool dp[21][1 << 20];
int a[21], b[21], sum[1 << 14];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    int n,m; cin >> n >> m;
    for (int i = 1; i <= n; cin >> a[i++]);
    for (int i = 0; i < m; cin >> b[i++]);
    fill(dp[0], dp[0] + (1 << 14), true);

    for (int mask = 1; mask < 1 << m; mask++) {
        int lsb = mask & -mask;
        sum[mask] = sum[mask ^ lsb] + b[__lg(lsb)];
    }
    if (n == 1) {
        cout << (count(sum, sum + (1 << m), a[1]) ? "YES" : "NO");
        return 0;
    }

    for (int i = 1; i <= n; i++) {
        for (int mask = 0; mask < 1 << m; mask++) {
            int sub = mask;
            while (sub > 0) {
                if (sum[sub] == a[i])
                    dp[i][mask] |= dp[i-1][mask ^ sub];
                sub = (sub - 1) & mask;
            }
//            cout << i << " " << mask << " " << dp[i][mask] << "\n";
        }
    }
    cout << (dp[n][(1 << m) - 1] ? "YES" : "NO");
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...