제출 #1215739

#제출 시각아이디문제언어결과실행 시간메모리
1215739Braabebo10은행 (IZhO14_bank)C++20
100 / 100
388 ms172872 KiB
#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 (have == a[i])return dp[i][msk] = solve(i + 1, msk, 0);
        if (msk + 1 == (1LL << m) or have > a[i])return 0LL;
        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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...