제출 #997307

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
997307		Marszpace	은행 (IZhO14_bank)	C++14	71 / 100	1083 ms	86872 KiB

bank

/*
 * With a little appreciation, in a mostly hollow tone, she says, "Delightful." As if the world has any meaning.
 * TASK : Bank
 * AUTHOR : Marszpace
*/

#include<bits/stdc++.h>
using namespace std;

int n,m;
vector<int> ppl(20);
vector<int> notes(20);

vector<vector<int>> dp(20,vector<int>((1<<20),2));
bool recur(int p, int s){
  //cout << p << " " << s << endl;
  if(p==n){return true;}
  if(dp[p][s]!=2){return dp[p][s];}
  for(int nexts=0;nexts<(1<<m);nexts++){
    if((nexts|s)!=nexts){continue;}
    int val=0;
    for(int i=0;i<m;i++){
      if((s&(1<<i))==0&&(nexts&(1<<i))==(1<<i)){
        val+=notes[i];
      }
    }
    if(val==ppl[p]){
      bool res=recur(p+1,nexts);
      if(res){dp[p][s]=1;return true;}
    }
  }
  dp[p][s]=0;
  return false;
}

int main(){
  ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  cin >> n >> m;
  for(int i=0;i<n;i++){
    cin >> ppl[i];
  }
  for(int i=0;i<m;i++){
    cin >> notes[i];
  }

  cout << (recur(0,0)?"YES":"NO");
  return 0;
}

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