Submission #1122920

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122920		ardadut	Bank (IZhO14_bank)	C++20	100 / 100	164 ms	17092 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<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();
    }
    
}

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