Submission #826150

#TimeUsernameProblemLanguageResultExecution timeMemory
826150NhanBeoo은행 (IZhO14_bank)C++17
100 / 100
183 ms14480 KiB
#include <bits/stdc++.h>
using namespace std;

#define int ll
#define MAX LLONG_MAX
#define st first
#define nd second
#define endl '\n'
#define SZ(x) ((int)x.size())
#define ALL(x) x.begin(), x.end()
typedef long long ll;
typedef pair< int, int > ii;
typedef pair< int, ii > iii;
typedef vector< int > vi;
typedef vector< ii > vii;
typedef vector< iii > viii;
typedef vector< vi > vvi;
typedef vector< vii > vvii;
typedef vector< viii > vviii;

const int N = 25;
int n, m, a[N], b[N], sum[1 << N];
bool vis[N][1 << N];
vi avai[N];

void dfs(int i, int state){
	if(i == n){
		cout << "YES";
		exit(0);
	}
	if(vis[i][state]) return;
	vis[i][state] = true;
	for(auto tmp: avai[i]){
		if(state & tmp) continue;
		dfs(i+1, state|tmp);
	}
}

signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin >> n >> m;
	for(int i=0; i<n; i++) cin >> a[i];
	for(int i=0; i<m; i++) cin >> b[i];
	for(int state=0; state<(1<<m); state++){
		// for(int i=0; (1<<i)<=state; i++){
			// if((state & (1<<i)) == 0){
				// sum[state | (1<<i)] = sum[state] + b[i];
			// }
		// }
		// for(int i=0; i<n; i++){
			// if(sum[state] == a[i]){
				// avai[i].emplace_back(state);
			// }
		// }
		int sum = 0;
		for(int i=0; (1<<i)<=state; i++){
			if(state & (1<<i)) sum += b[i];
		}
		for(int i=0; i<n; i++){
			if(sum == a[i]) avai[i].emplace_back(state);
		}
	}
	dfs(0, 0);
	cout << "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...