#include <bits/stdc++.h>
/// kitsune
using namespace std;
#define fi first
#define se second
#define mp make_pair
//#define int long long
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define rep(i, l, r) for (int i = (int)(l); i <= (int)(r); i++)
#define per(i, r, l) for (int i = (int)(r); i >= (int)(l); i--)
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
template<typename _Tp> bool minimize(_Tp& __a, const _Tp& __b) { if (__a > __b) { __a = __b; return true; } return false; }
template<typename _Tp> bool maximize(_Tp& __a, const _Tp& __b) { if (__a < __b) { __a = __b; return true; } return false; }
const int siz = 1e5 + 2;
const int SIZ = 1e6 + 2;
const int mod = 1e9 + 7;
const int maxx = 2e9;
const ll MAXX = 1e18;
const string file = "1";
int a[24], b[24];
int s[1 << 24];
bool dp[1 << 24];
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
// if (fopen((file + ".inp").c_str(), "r")) {
// freopen((file + ".inp").c_str(), "r", stdin);
// freopen((file + ".out").c_str(), "w", stdout);
// }
int n, m;
cin >> n >> m;
rep (i, 0, n - 1) {
cin >> a[i];
}
rep (i, 0, m - 1) {
cin >> b[i];
}
sort(a, a + n);
sort(b, b + m);
for (int i = 0, j = 0; i < n && j < m; i++) {
while (j < m && b[j] < a[i]) {
j++;
}
if (j < m && b[j] == a[i]) {
b[j] = a[i] = -1;
j++;
}
}
for (int i = 0, j = 0; j < n; i++) {
if (a[i] != -1) {
continue;
}
maximize(j, i + 1);
while (j < n && a[j] != -1) {
j++;
}
if (j == n) {
n = i;
break;
}
swap(a[i], a[j]);
}
for (int i = 0, j = 0; j < m; i++) {
if (b[i] != -1) {
continue;
}
maximize(j, i + 1);
while (j < m && b[j] != -1) {
j++;
}
if (j == m) {
m = i;
break;
}
swap(b[i], b[j]);
}
rep (i, 0, n - 1) {
a[i] += (i == 0 ? 0 : a[i - 1]);
}
rep (mask, 1, (1 << m) - 1) {
int k = __builtin_ctz(mask);
s[mask] = s[mask ^ (1 << k)] + b[k];
}
per (mask, (1 << m) - 1, 0) {
int pos = upper_bound(a, a + n, s[mask]) - a;
if (pos == n) {
dp[mask] = true;
continue;
}
dp[mask] = false;
for (int tmp = ((1 << m) - 1) ^ mask, i = __builtin_ctz(tmp); tmp; tmp ^= 1 << i, i = __builtin_ctz(tmp)) {
int new_mask = mask ^ (1 << i);
if (s[new_mask] <= a[pos]) {
dp[mask] |= dp[new_mask];
}
}
}
cout << (dp[0] ? "YES" : "NO") << "\n";
// cerr << "Time: " << 1000 * clock() / CLOCKS_PER_SEC << " ms\n";
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |