제출 #658073

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
658073		Melika0gh	은행 (IZhO14_bank)	C++17	100 / 100	132 ms	8604 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]; 
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';
}

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