제출 #826150

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
826150		NhanBeoo	은행 (IZhO14_bank)	C++17	100 / 100	183 ms	14480 KiB

bank

#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";
} 

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