Submission #489627

#TimeUsernameProblemLanguageResultExecution timeMemory
489627joe_goldberg은행 (IZhO14_bank)C++17
100 / 100
241 ms86556 KiB
#include<bits/stdc++.h>
using namespace std;
int dp[21][(1<<20)+10];
int cnt(int i,int mask,int salary[],int notes[],int n,int m,int val){
  if(i==n){
    return 1;
  }
  else if(dp[i][mask]!=-1){return dp[i][mask];}
  int ans=0;
  for(int j=0;j<m;j++){
    if(mask&(1<<j)){continue;}
    if(notes[j]<val){
      ans|=cnt(i,mask|(1<<j),salary,notes,n,m,val-notes[j]);
    }
    if(notes[j]==val){
      ans|=cnt(i+1,mask|(1<<j),salary,notes,n,m,salary[i+1]);
    }
  }
  return dp[i][mask]=ans;
}
int main(){
  int n,m;cin>>n>>m;int salary[n+1],notes[m+1];
  for(int i=0;i<n;i++){cin>>salary[i];}
  for(int i=0;i<m;i++){cin>>notes[i];}
  salary[n]=notes[m]=0;
  memset(dp,-1,sizeof(dp));
  int ans=cnt(0,0,salary,notes,n,m,salary[0]);
  (ans==1)?cout<< "YES":cout<< "NO";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...