제출 #660133

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
660133		envifly	은행 (IZhO14_bank)	C++17	52 / 100	1098 ms	828 KiB

bank

#include <bits/stdc++.h>
#ifndef LOCAL
#define debug(...) 0
#else
#include "../template/debug.cpp"
#endif

using namespace std;
using ll = long long;
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()

int main(){
	cin.tie(0) -> sync_with_stdio(0);
	int T = 1;
	// cin >> T;
	for(int _ = 0; _ < T; _++){
		int n, m; cin >> n >> m;
		vector<int> a(n+1), b(m);
		for(int i = 1; i <= n; i++) cin >> a[i];
		for(int i = 0; i < m; i++) cin >> b[i];
		vector<vector<bool>> can_make(n+1, vector<bool>(1<<m));
		for(int i = 1; i <= n; i++){
			for(int j = 0; j < (1 << m); j++){
				int sum = 0;
				for(int k = 0; k < m; k++){
					if(j & (1 << k)) sum += b[k];
				}
				if(sum == a[i]) can_make[i][j] = true;
			}
		}
		vector<vector<bool>> dp(n+1, vector<bool>(1<<m));
		dp[0][0] = true;
		for(int i = 1; i <= n; i++){
			for(int mask = 0; mask < (1 << m); mask++){
				for(int subset = mask; true; subset = (subset - 1) & mask){
					int non = (~subset) & mask;
					if(dp[i-1][subset] && can_make[i][non]) {
						dp[i][mask] = true;
						break;
					}
					if(subset == 0) break;
				}
			}
		}
		bool ok = false;
		for(int i = 0; i < (1 << m); i++){
			ok |= dp[n][i];
		}
		puts(ok ? "YES" : "NO");
	}
}

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