제출 #1325594

#제출 시각아이디문제언어결과실행 시간메모리
1325594csachy13Bank (IZhO14_bank)C++20
100 / 100
203 ms1424 KiB
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;

// int ind[1048600];
bool works[1048600];
int main() {
	// cin.tie(0); ios_base::sync_with_stdio(0);
	
	ll N, M;
	cin >> N >> M;
	vector<ll> X(N), Y(M), P(N + 1, LLONG_MAX);
	for (int i=0; i<N; i++) cin >> X[i];
	for (int i=0; i<M; i++) cin >> Y[i];
	P[0] = X[0];
	for (int i=1; i<N; i++) P[i] = X[i] + P[i - 1]; 
	
	works[0] = 1;
	
	// cout << "a\n";
	for (int i=0; i<1<<M; i++) {
		// cout << i << '\n';
		if (!works[i]) continue;
		
		ll sum = 0;
		for (int j=0; j<M; j++) {
			if ((i >> j) & 1) sum += Y[j];
		}
		
		if (sum >= P[N - 1]) continue;
		
		int k = 0;
		while (sum >= P[k]) k++;
		
		for (int j=0; j<M; j++) {
			if (((1 << j) | i) != i) {
				if (sum + Y[j] <= P[k]) {
					works[(1 << j) | i] = 1;
				}
			}
		}
	}
	
	for (int i=0; i<1<<M; i++) {
		if (!works[i]) continue;
		ll sum = 0;
		for (int j=0; j<M; j++) {
			if ((i >> j) & 1) sum += Y[j];
		}
		
		if (sum == P[N - 1]) {
			cout << "YES\n";
			return 0;
		}
	}
	
	cout << "NO\n";
	
	
	
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...