제출 #1056561

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1056561		vjudge1	은행 (IZhO14_bank)	C++14	100 / 100	70 ms	10872 KiB

bank

#include <bits/stdc++.h>
#define ii pair<int,int>
#define fi first
#define se second
using namespace std;

const int N = 21;
int n, m, a[N], b[N];
ii dp[1<<N];
bool vst[1<<N];

int main() {
	cin >> n >> m;
	for(int i = 1; i <= n; i++) cin >> a[i];
	for(int i = 0; i < m; i++) cin >> b[i];

	vst[0] = 1;
	dp[0] = {1, 0}; 
	for(int mask = 1; mask < (1 << m); mask++){
		for(int j = 0; j < m; j++){
			if(mask & (1 << j) && vst[mask ^ (1 << j)]){
				ii tmp = dp[mask ^ (1 << j)];
				tmp.se += b[j];
				if(tmp.se < a[tmp.fi]){
					vst[mask] = 1;
					dp[mask] = tmp;
				} else if(tmp.se == a[tmp.fi]){
					vst[mask] = 1;
                    dp[mask] = {tmp.fi + 1 , 0};
				}
			}
		}
	}
	for(int mask = 1; mask < (1 << m); mask++){
		if(dp[mask].fi > n){
			cout << "YES";
			return 0;
		}
	}
	cout << "NO";
}

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