제출 #1360599

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1360599		mydkn	은행 (IZhO14_bank)	C++17	100 / 100	69 ms	18360 KiB

bank

#include <bits/stdc++.h>

using namespace std;

#define tiii tuple<int, int, int>
#define em emplace

const int maxn = 25;

int n, m;
int a[maxn], b[maxn];
queue<tiii> qu;
bool vis[maxn][1<<20], res;

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin >> n >> m;
	for(int i=1;i<=n;++i){
		cin >> a[i];
		a[i] += a[i-1];
	}
	for(int i=0;i<m;++i) cin >> b[i];
	qu.em(1, 0, 0);
	vis[1][0] = 1;
	while(!qu.empty()){
		auto [u, mask, s] = qu.front();
		qu.pop();
		//fprintf(stderr, "%d %d %d\n", u, mask, s);
		if(u == n+1 && s == a[n]){
			res = 1;
			break;
		}
		for(int i=0;i<m;++i){
			if(mask & (1 << i) || s + b[i] > a[u]) continue;
			int nmask = mask | (1 << i), nu = u;
			if(s + b[i] == a[u]) ++nu;
			if(vis[nu][nmask]) continue;
			qu.em(nu, nmask, s + b[i]);
			vis[nu][nmask] = 1;
		}
	}
	cout << (res ? "YES" : "NO");
}

• 서브태스크 1: 19 / 19
• 서브태스크 2: 25 / 25
• 서브태스크 3: 27 / 27
• 서브태스크 4: 29 / 29