Submission #551087

#TimeUsernameProblemLanguageResultExecution timeMemory
551087fcw은행 (IZhO14_bank)C++17
100 / 100
115 ms8672 KiB
#include <bits/stdc++.h>
#define st first
#define nd second
using lint = int64_t;
constexpr int mod = 998244353;
constexpr int inf = 0x3f3f3f3f;
constexpr lint linf = 0x3f3f3f3f3f3f3f3f;
using namespace std;

int main() {
	cin.tie(nullptr)->sync_with_stdio(false);
	int n, m;
	cin>>n>>m;
	vector<int>a(n), b(m);
	for(int& i : a) cin>>i;
	for(int& i : b) cin>>i;
	vector<int>dp(1<<m, -1), cnt(1<<m, -1);
	dp[0] = cnt[0] = 0;
	for(int mask=0;mask<1<<m;mask++){
		if(dp[mask] == -1) continue;
		if(dp[mask] == n){
			cout<<"YES\n";
			return 0;
		}
		for(int i=0;i<m;i++){
			if(mask>>i&1) continue;
			if(cnt[mask] + b[i] < a[dp[mask]]){
				cnt[mask|(1<<i)] = cnt[mask] + b[i];
				dp[mask|(1<<i)] = dp[mask];
			}
			else if(cnt[mask] + b[i] == a[dp[mask]]){
				cnt[mask|(1<<i)] = 0;
				dp[mask|(1<<i)] = dp[mask] + 1;
			}
		}
	}
	cout<<"NO\n";



	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...