제출 #660133

#제출 시각아이디문제언어결과실행 시간메모리
660133enviflyBank (IZhO14_bank)C++17
52 / 100
1098 ms828 KiB
#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");
	}
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...