제출 #520145

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
520145		Cantfindme	은행 (IZhO14_bank)	C++17	100 / 100	112 ms	16836 KiB

bank

#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> pi;
#define f first
#define s second
#define FAST ios_base::sync_with_stdio(0); cin.tie(0);
#define all(x) x.begin(),x.end()
typedef pair<int, pi> pii;
 
const int maxn = 100;
const int INF = LLONG_MAX/2;

int n,m;
int A[maxn];
int B[maxn];
pi dp[(1 << 20)];

int32_t main() {
	FAST
	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 bm = 0; bm < (1 << m); bm++) {
		for (int i =0;i<m;i++) {
			if (((1 << i) & bm) == 0) continue;
			int prevbm = bm ^ (1 << i);
			
			auto [x, sum] = dp[prevbm];
			if (sum + B[i] == A[x]) {
				dp[bm] = max(dp[bm], pi(x + 1, 0));
			} else {
				dp[bm] = max(dp[bm], pi(x, sum + B[i]));
			}
		}
	}
	if (dp[(1<<m)-1].f == n) cout << "YES";
	else cout << "NO";
}

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