Submission #1293054

#TimeUsernameProblemLanguageResultExecution timeMemory
1293054redminote13proBank (IZhO14_bank)C++20
46 / 100
13 ms2596 KiB
#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")

#define McQueen ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define rep(i , a , n) for(int i = a; i < n; i++)
#define scan(a) for(auto & x : a) cin >> x;
#define rall(a) a.rbegin(), a.rend()
#define all(a) a.begin(), a.end()
#define double long double
#define int long long

using ll = long long;
using pii = pair<int , int>;
using ull = unsigned long long;

using vvi = vector<vector<int>>;
using vvc = vector<vector<char>>;

const ll mod = 1e9 + 7 , LOG = 20 , INF = 1e18 , N = 1e5 + 5 , K = 1 << 20;

ll gcd(ll a, ll b) {
	return b == 0 ? a : gcd(b, a % b);
}

inline void solve(){
	int n , m;
    cin >> n >> m;

    vector<int> a(n), b(m);
    scan(a);
    scan(b);

    vector<vector<int>> sub(n);

    for (int i = 0; i < n; i++) {
        for (int mask = 0; mask < (1 << m); mask++) {
            int sum = 0;
            for (int j = 0; j < m; j++) {
                if (mask & (1 << j)) sum += b[j];
            }
            if (sum == a[i]) sub[i].push_back(mask);
        }
        if (sub[i].empty()) {
            return cout << "NO\n" , void();
        }
    }

    vector<char> dp(1 << m, false);
    dp[0] = true;

    for (int i = 0; i < n; i++) {
        vector<char> ndp = dp;
        for (int mask = 0; mask < (1 << m); mask++) {
            if (!dp[mask]) continue;

            for (auto x : sub[i]) {
                if (mask & x) continue; 
                ndp[mask | x] = true;
            }
        }
        dp.swap(ndp);
    }

    for (int mask = 0; mask < (1 << m); mask++) {
        if (dp[mask]) {
            cout << "YES\n";
            return;
        }
    }

    cout << "NO\n";
}

signed main(){
//freopen("gcm.in", "r", stdin); freopen("gcm.out", "w", stdout);
	McQueen;
	int tt = 1;
	//cin >> tt;
	while(tt--) {
		solve();
	}
	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...