Submission #520145

#TimeUsernameProblemLanguageResultExecution timeMemory
520145CantfindmeBank (IZhO14_bank)C++17
100 / 100
112 ms16836 KiB
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> pi;
#define f first
#define s second
#define FAST ios_base::sync_with_stdio(0); cin.tie(0);
#define all(x) x.begin(),x.end()
typedef pair<int, pi> pii;
 
const int maxn = 100;
const int INF = LLONG_MAX/2;

int n,m;
int A[maxn];
int B[maxn];
pi dp[(1 << 20)];

int32_t main() {
	FAST
	cin >> n >> m;
	for (int i =0;i<n;i++) cin >> A[i];
	for (int i =0;i<m;i++) cin >> B[i];
	
	for (int bm = 0; bm < (1 << m); bm++) {
		for (int i =0;i<m;i++) {
			if (((1 << i) & bm) == 0) continue;
			int prevbm = bm ^ (1 << i);
			
			auto [x, sum] = dp[prevbm];
			if (sum + B[i] == A[x]) {
				dp[bm] = max(dp[bm], pi(x + 1, 0));
			} else {
				dp[bm] = max(dp[bm], pi(x, sum + B[i]));
			}
		}
	}
	if (dp[(1<<m)-1].f == n) cout << "YES";
	else cout << "NO";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...