Submission #489627

#	Time	Username	Problem	Language	Result	Execution time	Memory
489627		joe_goldberg	Bank (IZhO14_bank)	C++17	100 / 100	241 ms	86556 KiB

bank

#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";
}

• Subtask 1: 19 / 19
• Subtask 2: 25 / 25
• Subtask 3: 27 / 27
• Subtask 4: 29 / 29