제출 #684461

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
684461		GudStonks	은행 (IZhO14_bank)	C++17	100 / 100	215 ms	205832 KiB

bank

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll MOD = 1e9+7;
ll n, m, arr[25], brr[25], dp[25][(1<<20)];
vector<ll>ms[25];

ll rec(ll i, ll mask){
	if(i == 0)
		return dp[i][mask] = 1;
	if(dp[i][mask] != -1)
		return dp[i][mask];
	dp[i][mask] = 0;
	for(auto it : ms[i]){
		if((mask & it) == it)
			dp[i][mask] |= rec(i - 1, mask - it);
	}
	return dp[i][mask];
}

void fun(){
	cin>>n>>m;
	for(int i = 1; i <= n; i++)cin>>arr[i];
	for(int i = 1; i <= m; i++)cin>>brr[i];
	for(int i = 1; i < (1 << m); i++){
		ll sum = 0;
		for(int j = 0; (1 << j) <= i; j++)
			if(i & (1 << j))
				sum += brr[j + 1];
		for(int j = 1; j <= n; j++)
			if(sum == arr[j])
				ms[j].push_back(i);
	}
	memset(dp, -1, sizeof(dp));
	cout<<(rec(n, (1 << m) - 1) == 1 ? "YES\n" : "NO\n");
}
int  main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int ttt = 1;
	//cin>>ttt;
	while(ttt--)fun();
}

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