Submission #1215738

#	Time	Username	Problem	Language	Result	Execution time	Memory
1215738		Braabebo10	Bank (IZhO14_bank)	C++20	19 / 100	139 ms	16732 KiB

bank

#include<bits/stdc++.h>
#define ll long long
#define nl "\n"
#define all(v) v.begin(),v.end()
#define baraa ios_base::sync_with_stdio(false);cin.tie(NULL);
using namespace std;

int main() {
    baraa
    ll n, m;
    cin >> n >> m;
    vector<ll> a(n), b(m);
    for (ll &i: a)cin >> i;
    for (ll &i: b)cin >> i;
    vector<vector<ll> > dp(n, vector<ll>((1LL << m), -1));
    function<ll(ll, ll, ll)> solve = [&](ll i, ll msk, ll have) {
        if (i == n)return 1LL;
        if (msk + 1 == (1LL << m) or have > a[i])return 0LL;
        if (have == a[i])return dp[i][msk] = solve(i + 1, msk, 0);
        if (dp[i][msk] != -1) return dp[i][msk];
        ll ret = 0;
        for (ll j = 0; j < m; j++) {
            if (msk >> j & 1)continue;
            ret |= solve(i, msk | (1LL << j), have + b[j]);
        }
        return dp[i][msk] = ret;
    };
    cout << (solve(0, 0, 0) ? "YES" : "NO");
    return 0;
}

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