Submission #1001611

#	Time	Username	Problem	Language	Result	Execution time	Memory
1001611		vjudge1	은행 (IZhO14_bank)	C++17	100 / 100	97 ms	8616 KiB

bank

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second

pair<int, int> dp[1 << 20];
int a[20], b[20];

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int n, m; cin >> n >> m;
	for (int i = 0; i < n; ++i) cin >> a[i];
	for (int i = 0; i < m; ++i) cin >> b[i];
	pair<int, int> candi;
	for (int msk = 1; msk < (1 << m); ++msk) {
		for (int bit = 0; bit < m; ++bit) if (msk & (1 << bit)) {
			candi = dp[msk ^ (1 << bit)];
			if (candi.se + b[bit] == a[candi.fi]) ++candi.fi, candi.se = 0;
			else if (b[bit] == a[candi.fi]) ++candi.fi;
			else candi.se += b[bit]; 
			dp[msk] = max(dp[msk], candi);
			if (dp[msk].fi == n) {cout << "YES"; return 0;}
		}
		// for (int i = 0; i < m; ++i) cout << (msk & (1 << i) ? 1 : 0);
		// cout << ' ' << dp[msk].fi << ' ' << dp[msk].se << '\n';
	}
	cout << "NO";
}

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