Submission #1092099

#TimeUsernameProblemLanguageResultExecution timeMemory
1092099___은행 (IZhO14_bank)C++17
100 / 100
95 ms16868 KiB
#include <bits/stdc++.h>
#define int long long int
#define ff first
#define ss second
#define FT ios_base::sync_with_stdio(false);cin.tie(0);
using namespace std;
const int maxn = 21;
int a[maxn] , b[maxn] , dp[1 << maxn] , leftover[1 << maxn];
signed main()
{
	FT;
	int n , m;
	cin >> n >> m;
	for (int i = 0 ; i < n ; i++)
	{
		cin >> a[i];
	}
	for (int i = 0 ; i < m ; i++)
	{
		cin >> b[i];
	}
	for (int i = 1 ; i < (1 << m) ; i++)
	{
		dp[i] = -1;
		leftover[i] = -1;
	}
	for (int mask = 1 ; mask < (1 << m) ; mask++)
	{
		for (int j = 0 ; j < m ; j++)
		{
			if (!((1ll << j) & mask)) continue;
			int tmp = mask ^ (1 << j);
			if (dp[tmp] == -1) continue;
			if (leftover[tmp] + b[j] < a[dp[tmp]])
			{
				dp[mask] = dp[tmp];
				leftover[mask] = leftover[tmp] + b[j];
			}
			else if (leftover[tmp] + b[j] == a[dp[tmp]])
			{
				dp[mask] = dp[tmp] + 1;
				leftover[mask] = 0;
			}
		}
		if (dp[mask] == n)
		{
			cout << "YES" << endl;
			return 0;
		}
	}
	cout << "NO" << endl;
	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...