Submission #1264650

#TimeUsernameProblemLanguageResultExecution timeMemory
1264650piolkBank (IZhO14_bank)C++20
100 / 100
269 ms14920 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...