Submission #1146299

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146299		andrejikus	Bank (IZhO14_bank)	C++17	100 / 100	282 ms	19704 KiB

bank

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void DBG() { cerr << "]" << endl; }
template<class H, class... T> void DBG(H h, T... t) { cerr << to_string(h); if(sizeof...(t)) cerr << ", "; DBG(t...); }
#define dbg(...) cerr << "[" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)

const int N = 21;
const int B = (1<<N);
bool dp[N][B];
int f[B];
int a[N], b[N];

bool solve() {
    int n, m; cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 0; i < m; i++) cin >> b[i];

    f[0] = 0;
    for (int mask = 1; mask < (1<<m); mask++) {
        int in = __builtin_ctz(mask);
        f[mask] = f[mask^(1<<in)] + b[in];
    }

    dp[0][0] = true;
    for (int i = 1; i <= n; i++) {
        vector<int> maske;
        for (int mask = 1; mask < (1<<m); mask++) {
            if (f[mask] == a[i])
                maske.push_back(mask);
        }
        for (int mask = 0; mask < (1<<m); mask++) {
            if (!dp[i-1][mask]) continue;
            for (auto t : maske) {
                if ((t & mask) != 0) continue;
                dp[i][mask^t] = true;
            }
        }
    }

    bool ok = false;
    for (int mask = 1; mask < (1<<m); mask++)
        ok |= dp[n][mask];
    return ok;
}

signed main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int t=1; //cin >> t;
    while (t--) {
        if(solve()) cout << "YES\n";
        else cout << "NO\n";
    }
}

/*
1 5
8
4 2 5 1 3

2 6
9 10
5 4 8 6 3 11
*/

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