Submission #531715

#	Time	Username	Problem	Language	Result	Execution time	Memory
531715		erke	Bank (IZhO14_bank)	C++11	100 / 100	219 ms	82512 KiB

bank

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

int n, m;

namespace sub_1 {
  void solve() {
    int s; cin >> s;
    vector<int> a(m);
    for (auto &i : a) {
      cin >> i;
    }
    for (int mask = 0; mask < (1 << m); mask++) {
      int sum = 0;
      for (int i = 0; i < m; i++) {
        if ((mask >> i) & 1) {
          sum += a[i];
        }
      }
      if (sum == s) {
        cout << "YES" << '\n';
        return;
      }
    }
    cout << "NO" << '\n';
  }
}

namespace sub_2_3 {
  void solve() {
    if (n > m) {
      cout << "NO" << '\n';
      return;
    }
    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<int> sum(1 << m);
    for (int mask = 1; mask < (1 << m); mask++) {
      for (int i = 0; i < m; i++) {
        if ((mask >> i) & 1) {
          sum[mask] += b[i];
        }
      }
    }
    vector<vector<bool>> dp(n + 1, vector<bool>(1 << m));
    dp[0][0] = 1;
    for (int i = 1; i <= n; i++)
    for (int mask = 1; mask < (1 << m); mask++)
    for (int subm = mask; subm > 0; subm = (subm - 1) & mask) {
      if (dp[i - 1][mask ^ subm] && sum[subm] == a[i]) {
        dp[i][mask] = 1;
        if (i == n) {
          cout << "YES" << '\n';
          return;
        }
      }
    }
    cout << "NO" << '\n';
  }
}

namespace sub_4 {
  const int N = 20;

  int a[N], b[N];
  vector<int> vec[N];
  int cal[N][1 << N];

  void brute(int n, int mask) {
    if (n == -1) {
      cout << "YES" << '\n';
      exit(0);
    }
    if (cal[n][mask]) return;
    cal[n][mask] = 1;
    for (auto &i : vec[n]) {
      if ((mask & i) == i) {
        brute(n - 1, mask ^ i);
      }
    }
  }
  void solve() {
    for (int i = 0; i < n; i++) {
      cin >> a[i];
    }
    for (int i = 0; i < m; i++) {
      cin >> b[i];
    }
    for (int mask = 1; mask < (1 << m); mask++) {
      int sum = 0;
      for (int i = 0; i < m; i++) {
        if ((mask >> i) & 1) sum += b[i];
      }
      for (int i = 0; i < n; i++) {
        if (sum == a[i]) vec[i].push_back(mask);
      }
    }
    memset(cal, 0, sizeof(cal));
    brute(n - 1, (1 << m) - 1);
    cout << "NO" << '\n';
  }
}

signed main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n >> m;
  if (n == 1 && m <= 20) sub_1::solve();
  else if (n <= 20 && m <= 14) sub_2_3::solve();
  else sub_4::solve();
}

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