Submission #1167978

#TimeUsernameProblemLanguageResultExecution timeMemory
1167978ZeroCoolBank (IZhO14_bank)C++20
100 / 100
309 ms35808 KiB
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define ld long double
#define all(v) v.begin(),v.end()
#define ar array

const int M = 1e6;
const int N = 4e5 + 20;
const int LOG = 61;
const int INF = 1e18;
const int MOD = 1e9 + 7;
const ld EPS = 1e-9;
inline void mm(int &x){x = (x % MOD + MOD) % MOD;}
inline void chmin(int &x, int y){x = min(x, y);}
inline void chmax(int &x, int y){x = max(x, y);}

#pragma GCC optimize("unroll-loops,O3")


void orz(){
    int n, m;
    cin>>n>>m;
    int A[n], B[m];
    for(int i = 0;i < n;i++)cin>>A[i];
    for(int i = 0;i < m;i++)cin>>B[i];
    map<int, vector<int> > mp;
    for(int msk = 0;msk < (1 << m);msk++){
        int sum = 0;
        for(int i = 0;i < m;i++){
            if((1 << i) & msk)sum += B[i];
        }
        mp[sum].push_back(msk);
    }
    bool dp[n + 1][(1 << m)];
    memset(dp, 0, sizeof dp);
    dp[0][0] = 1;
    for(int i = 0;i < n;i++){
        for(int msk = 0;msk < (1 << m);msk++){
            if(!dp[i][msk])continue;
            for(auto u: mp[A[i]]){
                if(u & msk)continue;
                dp[i + 1][msk | u] = 1;
            }
        }
    }
    bool ans = 0;
    for(int i = 0;i < (1 << m);i++)ans |= dp[n][i];
    if(ans)cout<<"YES";
    else cout<<"NO";
}

signed main(){ios_base::sync_with_stdio(false);cin.tie(0);
   
    int t = 1;
    //cin>>t;
    while(t--)orz();
} 
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...