Submission #1292976

#TimeUsernameProblemLanguageResultExecution timeMemory
1292976fatelessBank (IZhO14_bank)C++20
25 / 100
1098 ms33256 KiB
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;

#define speedup cin.tie(0)->sync_with_stdio(0)
#define bitcount(x) __builtin_popcountll(x)
#define lla(x) x.rbegin(), x.rend()
#define all(x) x.begin(), x.end()
#define Tp template<class T>
#define pb push_back
#define arr array

Tp using vc = vector<T>;
using pii = pair<int,int>;
using ld = long double;
using ll = long long;
using ull = unsigned long long;
using uint = unsigned int;

#define int ll
const int inf = 1e18;
inline void solve(){
    int n, m;
    cin >> n >> m;
    vc<int> a(n), b(m);
    vc<int> sum(1 << m);
    for(int&x : a) cin >> x;
    for(int&x : b) cin >> x;
    vc<vc<int>> dp((1 << n), vc<int>(1 << m));
    for(int mb = 0; mb < (1 << m); mb++) 
        for(int i = 0; i < m; i++)
            if(mb >> i & 1) sum[mb] += b[i];
    
    for(int ma = 0; ma < (1 << n); ma++) {
        for(int mb = 0; mb < (1 << m); mb++) {
            for(int sub = mb; sub; sub = (sub - 1) & mb) { 
                for(int i = 0; i < n; i++) 
                    if((ma >> i & 1) && a[i] == sum[sub]) 
                        dp[ma][mb] = max(dp[ma][mb], dp[ma ^ (1 << i)][mb ^ sub] + 1);
            }
        }
    } // 2^(n + m) + 3^m
    cout << (dp[(1 << n) - 1][(1 << m) - 1] >= n? "YES\n" : "NO\n");
}

signed main(){
    speedup;
    int t = 1;
    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...