Submission #863443

#TimeUsernameProblemLanguageResultExecution timeMemory
863443TheSilentEnigmaBank (IZhO14_bank)C++17
100 / 100
138 ms9044 KiB
#include <bits/stdc++.h>
#define pb push_back
#define dbg(x) cout << "reached here " << x << endl;
#define f first
#define s second
#define ll long long

using namespace std;
typedef pair<int, int> pii;

const int maxn = 21;
int a[maxn], b[maxn], dp[1<<maxn], ps[maxn], sum[1<<maxn];

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int n, m;
	cin >> n >> m;

	for (int i = 1; i <= n; ++i)
	{
		cin >> a[i];
		ps[i] = ps[i-1] + a[i];
	}

	for (int i = 1; i <= m; ++i)
		cin >> b[i];

	for (int i = 1; i <= (1<<m)-1; ++i)
	{
		int h = i, bit = 1;
		while(h)
		{
			if(h&1)
				sum[i] += b[bit];
			bit++; 
			h /= 2;
		}
	}

	int ans = 0;
	for (int i = 1; i <= (1<<m)-1; ++i)
	{
		for (int j = 0; j < m; ++j)
			if(i & (1<<j))
				dp[i] = max(dp[i], dp[i^(1<<j)]);
		
		if(sum[i] == ps[dp[i]+1])
			dp[i]++;

		ans = max(ans, dp[i]);
	}
	
	if(ans == n)
		cout << "YES" << endl;
	else
		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...