Submission #884275

#	Time	Username	Problem	Language	Result	Execution time	Memory
884275		turtletortles	Bank (IZhO14_bank)	C++17	100 / 100	407 ms	23400 KiB

bank

#include "bits/stdc++.h"
using namespace std;

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define endl '\n'
#define debug(x) std::cerr << #x << " = " << x << '\n';

template<typename T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<typename T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

constexpr int MOD = 1e9 + 7;
constexpr int INF = 0x3f3f3f3f;
constexpr long long LLINF = 0x3f3f3f3f3f3f3f3f;

#define int long long
bool dp[(1 << 20) + 3][22];
vector<int> consists[20];
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n, m; cin >> n >> m;
  vector<int> people(n), notes(m);
  for (auto& a : people) cin >> a;
  for (auto& a : notes) cin >> a;

  memset(dp, 0, sizeof(dp));
  for (int i = 0; i < (1 << m); i++) {
    int thing = 0;
    for (int j = 0; j < m; j++) {
      if (i & (1 << j)) thing += notes[j];
    }

    for (int j = 0; j < n; j++) {
      if (thing == people[j]) consists[j].push_back(i);
    }
  }

  dp[0][0] = true;
  for (int i = 0; i < n; i++) {
    for (int mask = 0; mask < (1 << m); mask++) {
      if (!dp[mask][i]) continue;
      for (auto thing : consists[i]) {
        if (!(thing & mask)) {  //no intersection
          dp[thing | mask][i + 1] = true;
        }
      }
    }
  }

  bool works = false;
  for (int i = 0; i < (1 << m); i++) {
    if (dp[i][n]) works = true;
  }

  cout << ((works) ? "YES" : "NO") << endl;
  return 0;
}

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