#include <bits/stdc++.h>
using namespace std;
#define int long long
// #define endl '\n'
#define ff first
#define ss second
#define pb push_back
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define ar array
const int MOD = 1e9 + 7,INF = 1e18, N = 2e5 + 5;
/*
5 2
1 2 2
2 3 2
3 4 2
4 5 2
*/
void solve(){
int n, m;
cin >> n >> m;
vector <int> a(n) , b(m);
for(int i = 0;i < n;i++){
cin >> a[i];
}
int sum = 0;
for(int i = 0;i < m;i++){
cin >> b[i];
sum += b[i];
}
vector <int> dp(sum + 1);
dp[0] = 1;
for(int i = 0;i < m;i++){
for(int j = sum;j >= b[i];j--){
dp[j] += dp[j - b[i]];
}
}
sort(rall(a));
vector <int> use(m);
for(int i = 0;i < n;i++){
if(dp[a[i]] == 0){
cout<<"NO"<<endl;
return;
}
int h = a[i];
for(int j = 0;j < m;j++){
if(h <= 0) break;
if(dp[h - b[i]] && !use[i]){
use[i] = 1;
h -= b[i];
}
}
vector <int> dp1(sum + 1);
for(int i = 0;i < m;i++){
for(int j = sum;j >= b[i];j--){
if(use[i]) continue;
dp1[j] += dp1[j - b[i]];
}
}
swap(dp1 , dp);
}
cout<<"YES"<<endl;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int ti = 1;
while (ti--) {
solve();
}
}
# | 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... |