제출 #1312232

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1312232		nolqf	은행 (IZhO14_bank)	C++20	52 / 100	1094 ms	7304 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 + 1), 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(2, vector<bool>(1 << m));
  dp[0][0] = true;
  for ( int i = 0; i < n; ++i ) {
    for ( int mask = 0; mask < (1 << m); ++mask ) {
      for ( auto cand : masks[a[i + 1]] ) {
        if ( (cand & mask) == 0 ) {
          dp[(i & 1) ^ 1][mask ^ cand] = (dp[(i & 1) ^ 1][mask ^ cand] | dp[i & 1][mask]);   
        }
      }
    }
    for ( int mask = 0; mask < (1 << m); ++mask ) {
      dp[i & 1][mask] = false;
    }
  }
  bool ok = false;
  for ( int mask = 0; mask < (1 << m); ++mask ) {
    ok |= dp[n & 1][mask];
  }
  cout << (ok ? "YES" : "NO");
  return 0;
}

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