Submission #884463

#TimeUsernameProblemLanguageResultExecution timeMemory
884463iag99Bank (IZhO14_bank)C++17
19 / 100
86 ms16864 KiB
#include "bits/stdc++.h"
#define fast ios_base::sync_with_stdio(0) , cin.tie(0) , cout.tie(0)
#define endl '\n'
#define int long long
#define f first
#define mp make_pair
#define s second
using namespace std;

//string m;


signed main()
{
    fast;
	 int n,m;
	 cin>>n>>m;
	 vector<int> a(n);
	 vector<int> b(m);
	 for(int i=0; i<n; i++)
	 {
		 cin>>a[i];
	 }
	 for(int i=0; i<m; i++)
	 {
		 cin>>b[i];
	 }
	 vector<int> leftover(1 << m, -1); //leftover amount after using banknotes in mask
	vector<int> people_covered(1 << m, -1); //max prefix of peopel we can cover with banknotes in mask
	leftover[0] = 0;
	people_covered[0] = 0;
	for(int mask=0; mask<(1<<m); mask++)
	{
		for(int i=0; i<m; i++)
		{
			if(!(mask & (1<<i))) continue;
			int pmask=mask^(1<<i);
			if(leftover[pmask]+b[i] < a[people_covered[pmask]])
			{
				people_covered[mask]=people_covered[pmask];
				leftover[mask]=leftover[pmask]+b[i];
			}
			else if(leftover[pmask]+b[i]==a[people_covered[pmask]])
			{
				people_covered[mask]=people_covered[pmask]+1;
				leftover[mask]=0;
			}
		}
		if(people_covered[mask]==n)
		{
			cout<<"YES"<<endl;
			return 0;
		}
	}
	cout<<"NO"<<endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...