Submission #997302

#	Time	Username	Problem	Language	Result	Execution time	Memory
997302		Marszpace	Bank (IZhO14_bank)	C++14	71 / 100	1065 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++){
    int val=0,valid=1;
    for(int i=0;i<m;i++){
      if((s&(1<<i))==0&&(nexts&(1<<i))==(1<<i)){
        val+=notes[i];
      }
      if((s&(1<<i))==(1<<i)&&(nexts&(1<<i))==0){
        valid=0;
      }
    }
    //cout << nexts << " " << val << " " << valid << endl;
    if(valid&&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