Submission #1292971

#TimeUsernameProblemLanguageResultExecution timeMemory
1292971redminote13proBank (IZhO14_bank)C++20
44 / 100
1098 ms17480 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;

    if(n == 1){
		int used = 0;

		for(auto x : a){
			bool flag = false;

			for(int mask = 0; mask < (1 << m); mask++){
				if(mask & used) continue;

				int sum = 0;
				for(int j = 0; j < m; j++){
					if(mask & (1 << j)) sum += b[j];
				}

				if(sum == x){
					used |= mask; 
					flag = true;
					break;
				}
			}

			if(!flag){
				cout << "NO\n";
				return;
			}
		}

		cout << "YES\n";
	}
	else{
		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...