Submission #1245463

#TimeUsernameProblemLanguageResultExecution timeMemory
1245463greenbinjackBank (IZhO14_bank)C++20
100 / 100
158 ms8644 KiB
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
 
#include <bits/stdc++.h>
using namespace std;
 
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
 
using LL = long long;
 
#define all(V) V.begin(), V.end()
 
template <typename DT> using ordered_set = tree <DT, null_type, less <DT>, rb_tree_tag, tree_order_statistics_node_update>;
template <typename DT> using minheap = priority_queue < DT, vector <DT>, greater <DT> >;
template <class T> bool chMax (T &x, T y) { return y > x ? x = y, 1 : 0; }
template <class T> bool chMin (T &x, T y) { return y < x ? x = y, 1 : 0; }

const int N = 20;

int a[N], b[N], sumMask[1 << N], dp[1 << N];

int main() {
  cin.tie (nullptr) -> ios_base ::  sync_with_stdio (false);

  int n, m;
  cin >> n >> m;
  for (int i = 0; i < n; i++) cin >> a[i];
  for (int j = 0; j < m; j++) cin >> b[j];

  for (int mask = 0; mask < (1 << m); mask++) {
    for (int i = 0; i < m; i++) {
      if ((mask >> i) & 1) sumMask[mask] += b[i];
    }
  }

  dp[0] = 1;
  for (int i = 0, need = 0; i < n; i++) {
    need += a[i];
    for (int mask = 0; mask < (1 << m); mask++) {
      if (not dp[mask]) continue;
      for (int j = 0; j < m; j++) {
        dp[mask | (1 << j)] = 1;
      }
      dp[mask] &= (sumMask[mask] == need);
    }
  }

  cout << (accumulate (dp, dp + (1 << m), 0) > 0 ? "YES" : "NO") << '\n';

  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...