Submission #1328806

#TimeUsernameProblemLanguageResultExecution timeMemory
1328806rainerevan_Bank (IZhO14_bank)C++20
25 / 100
1095 ms548 KiB
#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

typedef long long ll;
const ll INF = 1e18;
const ll MOD = 1e9 + 7;
const ll MAXN = 2e6 + 5;
const ll LOG = 30;
#define vll vector <ll>
#define pll pair <ll, ll>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << " " << (x) << endl;

ll n, m;
ll a [30], b [30];
bool dp [30][MAXN];

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for(ll i = 0; i < n; i++){
        cin >> a[i];
    }
    for(ll i = 0; i < m; i++){
        cin >> b[i];
    }
    ll tot = (1<<m);
    for(ll i = 0; i < n; i++){
        for(ll j = 0; j < tot; j++){
            // debug(j)
            for(ll k = j; k > 0; k = (k-1) & j){
                // debug(k)
                ll cnt = 0;
                for(ll o = 0; o < m; o++){
                    if((j>>o) & 1 && !((k>>o) & 1)){
                        cnt += b[o];
                    }
                }
                if(cnt == a[i]){
                    if(i) dp[i][j] |= dp[i-1][k];
                }
            }
            ll cnt = 0;
            for(ll o = 0; o < m; o++){
                if((j>>o) & 1){
                    cnt += b[o];
                }
            }
            if(cnt == a[i]){
                if(i) dp[i][j] |= dp[i-1][0];
                else dp[i][j] = 1;
            }
            // cout << i << " << ";
            // for(ll o = 0; o < m; o++){
            //     cout << ((j>>o) & 1);
            // }
            // cout << " << " << dp[i][j] << endl;
        }
    }
    ll ans = 0;
    for(ll i = 0; i < tot; i++) ans |= dp[n-1][i];
    if(ans) cout << "YES" << endl;
    else cout << "NO" << endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...