제출 #997305

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
997305		Marszpace	은행 (IZhO14_bank)	C++14	25 / 100	1059 ms	452 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 main(){
  ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  int n,m;
  cin >> n >> m;
  vector<int> ppl(n);
  vector<int> notes(m);
  for(int i=0;i<n;i++){
    cin >> ppl[i];
  }
  for(int i=0;i<m;i++){
    cin >> notes[i];
  }

  vector<vector<bool>> dp(n+1,vector<bool>((1<<m),false));
  
  for(int s=0;s<(1<<m);s++){
    dp[n][s]=true;
  }

  for(int p=n-1;p>=0;p--){
    for(int s=0;s<(1<<m);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]){
          if(dp[p+1][nexts]){dp[p][s]=true;}
        }
      }
    }
  }

  cout << (dp[0][0]?"YES":"NO");
  return 0;
}

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