제출 #1034904

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1034904		pera	은행 (IZhO14_bank)	C++17	100 / 100	204 ms	181080 KiB

bank

#include<bits/stdc++.h>
using namespace std;
const int N = 20 + 1 , M = 20000 + 1;
int n , m;
vector<int> x(N) , y(N);
vector<vector<int>> dp(N , vector<int>(1 << N)) , msk(M);
void solve(int u , int MASK){
   if(u == n + 1){
      cout << "YES";
      exit(0);
   }
   if(dp[u][MASK]){
      return;
   }
   dp[u][MASK] = 1;
   for(int mask : msk[x[u]]){
      if((mask & MASK) == 0){
         solve(u + 1 , MASK | mask);
      }
   }
}
int main(){
   cin >> n >> m;
   for(int i = 1;i <= n;i ++){
      cin >> x[i];
   }
   for(int i = 1;i <= m;i ++){
      cin >> y[i];
   }
   for(int mask = 0;mask < (1 << m);mask ++){
      int sum = 0;
      for(int x = 0;x < m;x ++){
         if(mask >> x & 1){
            sum += y[x + 1];
         }
      }
      msk[sum].push_back(mask);
   }
   solve(1 , 0);
   cout << "NO" << endl;
}

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