Submission #1103082

#TimeUsernameProblemLanguageResultExecution timeMemory
1103082hippo123Bank (IZhO14_bank)C++17
100 / 100
96 ms8700 KiB
#include <bits/stdc++.h>
using namespace std;

#define pr pair<int, int>
#define ll long long
#define pb push_back
#define f first
#define s second

int main(){
	//freopen("bank.in", "r", stdin);
	//freopen("bank.out", "w", stdout);
	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<pr> dp(1<<m); // .f number of people covered, .s: remaining bills
	dp[0]={0, 0};
	
	for (int x=0; x<(1<<m); x++){
		for (int i=0; i<m; i++){
			if(x&(1<<i)) continue;
			
			pr node; 
			if(a[dp[x].f]==dp[x].s+b[i]) node={dp[x].f+1, 0};
			else {
				node={dp[x].f, dp[x].s+b[i]};
			}
			
			dp[x|(1<<i)]=max(dp[x|(1<<i)], node);
		}
	}
	if(dp[(1<<m)-1].f==n) cout<<"YES"<<endl;
	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...