Submission #1001451

#TimeUsernameProblemLanguageResultExecution timeMemory
1001451anHiep은행 (IZhO14_bank)C++14
71 / 100
1040 ms32348 KiB
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pb push_back
#define fi first
#define se second

const int oo = 1e18;
const int maxn = 1e5 + 10;

bool dp[23][1<<20];
int s[1<<20];
vector<int> f[23];

void solve(){
    int n, m;
    cin >> n >> m;
    vector<int> a(n + 1), b(m);
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 0; i < m; i++) cin >> b[i];
    for(int j = 0; j < (1<<m); j++){
        int sum = 0;
        for(int i = 0; i < m; i++){
            if(j&(1<<i)) sum+=b[i];
        }
        s[j] = sum;
    }
    for(int i = 1; i <= n; i++){
        for(int j = 0; j < (1<<m); j++){
            if(s[j] == a[i]){
                    f[i].pb(j);
            }
        }
    }
    memset(dp,0, sizeof(dp));
    dp[0][0] = 1;
    bool c = 0;
    for(int i = 1; i <= n; i++){
        for(int j = 0; j < (1<<m); j++){
                for(auto x: f[i]) if((x&j)==x)dp[i][j] |= dp[i - 1][j ^ x];
                if(i == n && dp[i][j]){
                    c = 1; break;
                }
        }
    }
    if(c) cout<<"YES";
    else cout<<"NO";
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    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...