제출 #1115800

#제출 시각아이디문제언어결과실행 시간메모리
1115800nanghongg은행 (IZhO14_bank)C++14
52 / 100
1054 ms21328 KiB
#include<bits/stdc++.h>
using namespace std;

#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx,avx2,fma")

#define ll long long
#define ld long double

#define PI 3.1415926535897932384626433832795l;

ll a[21]; ll b[21];
bool dp[21][1<<21];

void solve(){
    ll n,m; cin >> n >> m;
    map<ll,ll>mp;
    for (ll i=1; i<=n; i++){
        cin >> a[i];
        mp[a[i]]++;
    }
    vector<vector<ll>>can(1001);
    for (ll i=0; i<m; i++) cin >> b[i];
    for (ll mask=0; mask<(1<<m); mask++){
        ll sum=0;
        for (ll i=0; i<m; i++){
            if (mask&(1<<i)){
                sum+=b[i];
            }
        }
        if (mp[sum]) can[sum].push_back(mask);
    }
    dp[0][0]=true;
    for (ll i=1;i<=n; i++){
        for (ll mask=0; mask<(1<<m); mask++){
            for (auto can_mask:can[a[i]]){
                if ((can_mask&mask)!=can_mask) continue;
                ll pre_mask=(can_mask^mask);
                if (dp[i-1][pre_mask]) {dp[i][mask] = true; break;}
            }
        }
    }
    for (ll mask=0; mask<(1<<m); mask++){
        if (dp[n][mask]){
            cout <<"YES";
            return;
        }
    }
    cout << "NO";
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int tc = 1;
    // cin >> tc;
    for (int t = 1; t <= tc; t++) {
        // cout << "Case #" << t << ": ";
        solve();
    }
}

#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...