Submission #1166266

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166266		SulA	Bank (IZhO14_bank)	C++20	52 / 100	50 ms	584 KiB

bank

#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 << 14];
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;
    assert(m <= 14);
    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)];
    }

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

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