#include <bits/stdc++.h>
using namespace std;
int main(){
//my first bitmask dp
int n,m;
cin>>n>>m;
vector<int> salaries(n);
vector<int> banknotes(m);
for (int i=0;i<n;i++) cin>>salaries[i];
for (int i=0;i<m;i++) cin>>banknotes[i];
int subsets=(1<<m);
vector<int> subsetSum(subsets,0);
subsetSum[0]=0;
for (int mask=1;mask<subsets;mask++){
int lowestBit=mask & -mask;
int j=0; //the number of the smallest bit
while (lowestBit!=(1<<j)) j++;
subsetSum[mask]=subsetSum[mask ^ lowestBit]+banknotes[j];
}
vector<vector<int>> goodSubsets(1007); // goodSubsets[sum]={all subsets with sum}
for (int mask=1;mask<subsets;mask++){
if (subsetSum[mask]<=1000) goodSubsets[subsetSum[mask]].push_back(mask);
}
vector<int> paid(subsets,-1); // paid[subset] - what prefix of salaries was paid with subset
paid[0]=0;
bool ok=false;
for (int mask=0;mask<subsets;mask++){ //mask=subset of banknotes used
if (paid[mask]==-1) continue;
int next=paid[mask]; //next salary to pay after using banknotes mask;
if (next>=n) continue;
for (int subset:goodSubsets[salaries[next]]){ //all of the subsets with sum=salary
if ((mask&subset)==0){ //none that have been used are being used again
int newMask=mask|subset; //mask after using the banknotes
paid[newMask]=max(paid[newMask],next+1);
if (paid[newMask]==n) ok=true;
}
}
}
if (ok) cout<<"YES";
else cout<<"NO";
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... |