Submission #483535

#TimeUsernameProblemLanguageResultExecution timeMemory
483535YomapeedBank (IZhO14_bank)C++17
71 / 100
1093 ms16840 KiB
#include<bits/stdc++.h>
#define pi 3.141592653589793238
#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#define MOD 1000000007
#define INF 999999999999999999 
#define pb push_back
#define ff first
#define ss second
 
#define mt make_tuple
#define printclock cerr<<"Time : "<<1000*(long double)clock()/(long double)CLOCKS_PER_SEC<<"ms\n";
#define ll long long
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>

using namespace __gnu_pbds;
 
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll rand(ll B) { return (unsigned ll)rng() % B;}

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 
int main() {
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    fast;
    ll _T = 1;
    
    //cin >> _T;
    while (_T--) {
        ll N, M;
        cin >> N >> M;
        vector<ll> a(N), b(M);
        for(int i = 0; i < N; i++) cin >> a[i];
        for(int i = 0; i < M; i++) cin >> b[i];

        vector<ll> sum(1 << M);
        for(int i = 0; i < (1 << M); i++){
            for(int j = 0; j < M; j++){
                if(i & (1 << j)){
                    sum[i] += b[j];
                }
            }
        }
        vector<ll> dp(1 << M, -INF);
        dp[0] = 0;
        for(int mask = 0; mask < (1 << M); mask++){
            ll curr = dp[mask];
            if(curr == -INF){
                continue;
            }
            if(curr == N){
                cout << "YES\n";
                return 0;
            }
            ll m = 0;
            for(int j = 0; j < M; j++){
                if(mask & (1 << j)){
                    continue;
                }
                m ^= (1 << j);
            }
            for (int s = m; ; s = (s - 1) & m) {
                if(sum[s] == a[curr]){
                    dp[mask ^ s] = max(dp[mask ^ s], curr + 1);
                }
                
                if (s == 0){
                    break;
                }
            }
        }
        cout << "NO\n";
    }
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...