Submission #1303626

#TimeUsernameProblemLanguageResultExecution timeMemory
1303626zhenBank (IZhO14_bank)C++17
100 / 100
97 ms16864 KiB
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    // freopen("template.in", "r", stdin);
    // freopen("template.out", "w", stdout);
    
    ll n, m; cin >> n >> m;
    vector<ll> a(n), b(m); for (ll i = 0; i < n; ++i){cin >> a[i];} for (ll i = 0; i < m; ++i){cin >> b[i];}
    vector<ll> done(1 << m, -1); vector<ll> left(1 << m,  -1);
    done[0] = 0; left[0] = 0; 
    
    for (ll s = 1; s < (1 << m); ++s){
        for (ll i = 0; i < m; ++i){
            if (!(s & (1 << i))){continue;}
            ll k = s - (1 << i);
            if (left[k] + b[i] == a[done[k]]){
                if (done[k] > done[s]){
                    done[s] = done[k] + 1;
                    left[s] = 0;
                }
            }
            else {
                if (done[k] > done[s]){
                    done[s] = done[k];
                    left[s] = left[k] + b[i];
                }
            }
        }
        if (done[s] == n){
            cout << "YES"; return 0;
        }
    }
    cout << "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...