제출 #1122918

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1122918		ardadut	은행 (IZhO14_bank)	C++20	71 / 100	1095 ms	11204 KiB

bank

#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<ll> mask_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(ll i = 1 ; i <= (1<<m) - 1 ; i++){
        if((i & mask) == i and mask_val[i] == person[person_no]){
            dp_func(person_no+1,mask ^ i);
        }
    }

    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));
    mask_val.resize(1<<m,0);

    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++){
        for(ll j = 0 ; j <= m-1 ; j++){
            if(i & (1<<j)){
                mask_val[i] += banknot[j+1];
            }
        }
    }

    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();
    }
    
}

• Subtask 1: 19 / 19
• Subtask 2: 25 / 25
• Subtask 3: 27 / 27
• Subtask 4: 0 / 29