제출 #826099

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
826099		NhanBeoo	은행 (IZhO14_bank)	C++17	19 / 100	86 ms	10724 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 dp[N][1 << N], vis[N][1 << N];
vi avai[N];

bool dfs(int i, int state){
	if(vis[i][state]) return dp[i][state];
	vis[i][state] = true;
	if(i == n) return dp[i][state] = true;
	bool ans = false;
	for(auto tmp: avai[i]){
		if(state & tmp) continue;
		ans |= dfs(i+1, state|tmp);
	}
	return dp[i][state] = ans;
}

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);
			}
		}
	}
	cout << (dfs(0, 0) ? "YES" : "NO");
} 

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