Submission #658073

#TimeUsernameProblemLanguageResultExecution timeMemory
658073Melika0ghBank (IZhO14_bank)C++17
100 / 100
132 ms8604 KiB
#include<bits/stdc++.h>
using namespace std;

const int maxn = 22, maxb = (1 << maxn);
int a[maxn], b[maxn], dp[maxb], left_val[maxb]; 
int n, m;

int main()
{
	cin >> n >> m;
	for(int i = 0; i < n; i++)
		cin >> a[i];
	for(int i = 0; i < m; i++)
		cin >> b[i];
	
	bool ch = 0;
	for(int mask = 1; mask < (1 << m); mask++)
	{
		dp[mask] = 0;
		//cout << mask << " : " << endl;
		for(int i = 0; i < m; i++)
		{
			if(((mask >> i) & 1))
			{
				int mask2 = mask ^ (1 << i);
				int tmp = dp[mask2];
				int val = left_val[mask2] + b[i];
				if(val > a[tmp])
					continue;
				
			//	cout << mask2 << " , " << left_val[mask2] << endl;
				if(tmp + (val == a[tmp]) >= dp[mask])
				{
					dp[mask] = tmp + (val == a[tmp]);
					left_val[mask] = (val == a[tmp]) ? 0 : val;
				}
			}
		}
		if(dp[mask] == n)
			ch = true;
	}
	
	if(ch)
		cout << "YES" << '\n';
	else
		cout << "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...