Submission #1171479

#TimeUsernameProblemLanguageResultExecution timeMemory
1171479nguyenkhangninh99Bank (IZhO14_bank)C++20
100 / 100
110 ms16712 KiB

#include <bits/stdc++.h>
using namespace std;

#define int long long

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int n, m; cin >> n >> m;
	vector<int> 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<int> left(1 << m, -1), dp(1 << m, -1);
	left[0] = dp[0] = 0;

    bool ok = false;

	for (int s = 0; s < (1 << m); s++) {
		for (int i = 0; i < m; i++) {
			if (!((s >> i) & 1)) continue; 
			int prev = s ^ (1 << i);
			if (dp[prev] == -1) continue;

			int cur = left[prev] + b[i];
			if(cur < a[dp[prev]]) {
				dp[s] = dp[prev];
				left[s] = cur;
			}
		
			else if(cur == a[dp[prev]]){
				dp[s] = dp[prev] + 1;
				left[s] = 0;
			}
		}

		ok |= (dp[s] == n);
	}
	
    cout << (ok ? "YES\n" : "NO\n");
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...