| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1368620 | po_rag526 | 은행 (IZhO14_bank) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define nn endl
#define pb push_back
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<int> a(n), b(m);
for (int i = 0; i < n; i++) cin >> a[i];
for (int i = 0; i < m; i++) cin >> b[i];
vector<int> dp((1LL << m), -1), memo((1LL << m), -1);
dp[0] = 0;
memo[0] = 0;
for (int mask = 0; mask < N; mask++) {
if (dp[mask] == -1) continue;
int id = memo[mask];
if (id >= n) continue;
if (dp[mask] == a[id]) {
if (memo[mask] < id + 1) {
memo[mask] = id + 1;
dp[mask] = 0;
}
continue;
}
for (int i = 0; i < m; i++) {
if (mask & (1LL << i)) continue;
int ns = dp[mask] + b[i];
if (ns <= a[id]) {
int j = mask | (1LL << i);
if (memo[j] < id || (memo[j] == id && dp[j] < ns)) {
memo[j] = id;
dp[j] = ns;
}
}
}
}
bool ok = false;
for (int i = 0; i < (1LL << m); i++) {
if (memo[i] == n) {
ok = true;
break;
}
}
cout << (ok ? "YES" : "NO") << nn;
}