제출 #1312149

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1312149		nolqf	Bank (IZhO14_bank)	C++20	25 / 100	1095 ms	7388 KiB

bank

#include <bits/stdc++.h>

using namespace std;

const int DIM = 1e3;

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n, m;

  cin >> n >> m;
  vector<int> a(n), b(m);
  for ( int i = 1; i <= n; ++i ) cin >> a[i];
  for ( int i = 0; i < m; ++i ) cin >> b[i];
  vector<vector<int>> masks(1 + DIM, vector<int>());
  for ( int mask = 0; mask < (1 << m); ++mask ) {
    int val = 0;
    for ( int i = 0; i < m; ++i ) {
      if ( mask & (1 << i) ) {
        val += b[i]; 
      }
    }
    if ( val <= DIM ) {
      masks[val].push_back(mask); 
    }
  }
  vector<vector<bool>> dp(n + 1, vector<bool>(1 << m));
  dp[0][0] = true;
  for ( int i = 1; i <= n; ++i ) {
    for ( int mask = 1; mask < (1 << m); ++mask ) {
      for ( auto cand : masks[a[i]] ) {
        if ( (cand & mask) == cand ) {
          dp[i][mask] = (dp[i][mask] | dp[i - 1][mask ^ cand]);   
        }
      }
    }
  }
  bool ok = false;
  for ( int mask = 0; mask < (1 << m); ++mask ) {
    ok |= dp[n][mask];
  }
  cout << (ok ? "YES" : "NO");
  return 0;
}

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