Submission #1312231

#TimeUsernameProblemLanguageResultExecution timeMemory
1312231nolqfBank (IZhO14_bank)C++20
100 / 100
307 ms7348 KiB
#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 ) {
      if ( !dp[i & 1][mask] ) continue;
      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;
}

#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...