Submission #658071

#	Time	Username	Problem	Language	Result	Execution time	Memory
658071		Melika0gh	Bank (IZhO14_bank)	C++17	19 / 100	95 ms	9600 KiB

bank

#include<bits/stdc++.h>
using namespace std;

const int maxn = 22, maxb = (1 << maxn);
int a[maxn], b[maxn], dp[maxb], left_val[maxb]; 
bool mark[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];
	
	mark[0] = 1;
	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) && mark[mask ^ (1 << i)])
			{
				int mask2 = mask ^ (1 << i);
				int tmp = dp[mask2];
				if(left_val[mask2] + b[i] > a[tmp])
					continue;
				
			//	cout << mask2 << " , " << left_val[mask2] << endl;
				tmp += (left_val[mask2] + b[i] == a[tmp]);
				if(tmp >= dp[mask])
				{
					dp[mask] = tmp;
					left_val[mask] = (left_val[mask2] + b[i] == a[tmp]) ? 0 : left_val[mask2] + b[i];
				}
				mark[mask] = true;
			}
		}
		if(dp[mask] == n)
			ch = true;
	}
	
	if(ch)
		cout << "YES" << '\n';
	else
		cout << "NO" << '\n';
}

• Subtask 1: 19 / 19
• Subtask 2: 0 / 25
• Subtask 3: 0 / 27
• Subtask 4: 0 / 29