// #pragma GCC optimize("O3,Ofast,unroll-loops")
// #pragma GCC target("avx2")
#include<bits/stdc++.h>
#define ll long long
#define int ll
#define pii pair<int,int>
#define tiii tuple<int,int,int>
//#define bs bitset<1001>
using namespace std;
int32_t main(){
//bs nothing;
int n,m;
cin >> n >> m;
vector<int> sal(n),val(m);
for(int i = 0; i < n; i++){
cin >> sal[i];
}
for(int i = 0; i < m; i++){
cin >> val[i];
}
sort(val.begin(),val.end());
int p2 = (1<<m);
vector<int> dp(p2,-1);
//vector<bs> left(p2);
vector<int> left(p2,sal[0]);
dp[0] = 0;
left[0] =sal[0];
bool early = false;
for(int k = 1; k < p2; k++){
if(early) break;
for(int i = 0; i < m; i++){
if(dp[k] >= n) {
early = true;
break;
}
int cur = (1 << i);
if(k & cur){
bool pos = left[k-cur] == val[i];
if(pos && dp[k-cur]+1 > dp[k]){
dp[k] = dp[k-cur]+1;
if(dp[k] >= n) break;
left[k] = sal[dp[k]];
}else if(dp[k-cur] > dp[k]){
dp[k] = dp[k-cur];
left[k] = left[k-cur];
if(left[k-cur]-val[i] >= 0)left[k]-=val[i];
}
// else if(dp[k-cur] == dp[k]){
// if(left[k-cur]-val[i] >= 0)left[k] = min(left[k] ,left[k-cur]-val[i]);
// }
}
}
}
if(dp[p2-1] == n ||early){
cout << "YES\n";
}else{
cout << "NO\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... |