Submission #1274357

#TimeUsernameProblemLanguageResultExecution timeMemory
1274357bahy은행 (IZhO14_bank)C++20
100 / 100
424 ms78928 KiB
#include <bits/stdc++.h>
using namespace std;

int n, m, a[20], b[20], sum[1 << 20], vis[20][1 << 20], cur;
bool dp[20][1 << 20];
map<int, vector<int>>subs;

bool calc(int ind, int mask){
    if(ind == n)return true;
    bool &ret = dp[ind][mask];
    if(vis[ind][mask] == cur)return ret;
    vis[ind][mask] = cur;
    ret = false;
    for(auto msk: subs[a[ind]]){
        if(!(mask & msk))ret |= calc(ind+1, mask | msk);
    }
    return ret;
}

void solve(){
    cin>>n>>m;
    for(int i=0;i<n;i++)cin>>a[i];
    for(int i=0;i<m;i++)cin>>b[i];

    for(int mask = 0;mask < (1 << m); mask++){
        for(int i=0;i<m;i++){
            if(mask >> i & 1)sum[mask] += b[i];
        }
    }

    subs.clear();    
    for(int mask = 0; mask < (1 << m); mask++)subs[sum[mask]].push_back(mask);

    cur++;
    if(calc(0, 0))cout<<"YES\n";
    else cout<<"NO\n";
}

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

    int t = 1;
    // cin>>t;
    while(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...