This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pll pair<ll, ll>
#define ppll pair<pll, ll>
#define fll(i, n) for (ll i =0 ; i < n; i++)
#define vll vector<ll>
#define prtv(V) fll(i, V.size()) cout << V[i] << " "; cout << '\n';
ll INF = 2e18;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
ll n, m;
cin >> n >> m;
vll A(n), B(m); fll(i, n) cin >> A[i];
ll S = 0;
fll(i, m) { cin >> B[i]; S += B[i]; }
sort(B.begin(), B.end(), [](ll a, ll b) { return a > b; });
vector<pll> ans(1<<n, {0, INF});
ans[0] = {m, 0};
fll(s, (1<<n))
{
fll(i, n)
{
if (!(s&(1<<i)))
{
ll sum = 0, j = 0;
ll k = ans[s].second;
ll remNotes = ans[s].first;
while (j < m && A[i] > sum)
{
if ((k & (1<<j) )|| (B[j]+sum > A[i]))
{
j++;
continue;
}
sum += B[j];
remNotes--;
k = k & (1<<j);
j++;
}
if (sum < A[i]) continue;
if (ans[s|(1<<i)].first < remNotes)
ans[s|(1<<i)] = {remNotes, k};
}
}
}
if (ans[(1<<n)-1].second == INF) cout << "NO\n";
else cout << "YES\n";
}
# | 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... |