제출 #845939

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
845939		alexz1205	은행 (IZhO14_bank)	C++14	100 / 100	98 ms	6384 KiB

bank

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

const int N = 20;

int memoi[N][(1<<20)];

int arr1[N], arr2[N];
int n, m;

bool isPos(int i, int v, int d){
	if (memoi[i][d] != 0){
		return memoi[i][d]-1;
	}
	if (v == 0){
		if (i == n-1){
			return 1;
		}
		i ++;
		v = arr1[i];
		return isPos(i, v, d);
	}
	bool pos = 0;
	for (int x = 0; x < m; x ++){
		if (d&(1<<x)){
			if (arr2[x] <= v){
				if (isPos(i, v-arr2[x], d&(~(1<<x)))){
					pos = 1;
					break;
				}
			}else {
				break;
			}
		}
	}
//	if (v == arr1[i]){
		memoi[i][d] = pos+1;
//	}
	return pos;
}

int main() {
	cin >> n >> m;
	for (int x = 0; x < n; x ++){
		cin >> arr1[x];
	}
	for (int x = 0; x < m; x ++){
		cin >> arr2[x];
	}
	sort(arr1, arr1+n);
	sort(arr2, arr2+m);
	bool pos = isPos(0, arr1[0], (1<<m)-1);
	cout << (pos ? "YES" : "NO") << endl;
	return 0;
}

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