제출 #1122920

#제출 시각아이디문제언어결과실행 시간메모리
1122920ardadut은행 (IZhO14_bank)C++20
100 / 100
164 ms17092 KiB
#include <bits/stdc++.h>
    
#define ll long long
#define pb push_back
#define endl "\n"
#define vec vector<ll>
#define vecvec vector<vector<ll>>
    
using namespace std;
    
/*#define FileName ""
string Ghhhh = ".in";
string Ghhhhh = ".out";
ifstream Girdi(FileName + Ghhhh);
ofstream Cikti(FileName + Ghhhhh);
#define cin Girdi
#define cout Cikti*/

ll n,m;
vector<ll> person;
vector<ll> banknot;
vector<vector<bool>> dp;
vector<vector<ll>> val;

inline void dp_func(ll person_no, ll mask){

    if(person_no == n+1){
        cout << "YES" << endl;
        exit(0);
    }
    
    if(dp[person_no][mask] != 0) return;

    for(auto it : val[person[person_no]]){
        if((mask & it) == it){
            dp_func(person_no+1,mask ^ it);
        }
    }

    dp[person_no][mask] = 1;

}

inline void solve(){

    cin >> n >> m;

    person.resize(n+1);
    banknot.resize(m+1);
    dp.resize(n+1,vector<bool>((1<<m),0));
    val.resize(20005);

    for(ll i = 1 ; i <= n ; i++) cin >> person[i];
    for(ll i = 1 ; i <= m ; i++) cin >> banknot[i];

    for(ll i = 1 ; i <= (1<<m) - 1 ; i++){
        ll sum = 0;
        for(ll j = 0 ; j <= m-1 ; j++){
            if(i & (1<<j)){
                sum += banknot[j+1];
            }
        }
        val[sum].pb(i);
    }

    dp_func(1,(1<<m) - 1);

    cout << "NO" << endl;

}
    
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll 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...