Submission #531692

#	Time	Username	Problem	Language	Result	Execution time	Memory
531692		erke	Bank (IZhO14_bank)	C++11	46 / 100	1080 ms	372 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 {

  const int N = 15;

  int a[N], b[N], c[N];

  void check() {
    for (int i = 1; i <= m; i++) {
      if (c[i] != a[i]) return;
    }
    cout << "YES" << '\n';
    exit(0);
  }

  void brute(int i) {
    for (int j = 0; j <= n; j++) {
      c[j] += b[i];
      if (i == m) check();
      else brute(i + 1);
      c[j] -= b[i];
    }
  }

  void solve() {
    for (int i = 1; i <= n; i++) {
      cin >> a[i];
    }
    for (int i = 1; i <= m; i++) {
      cin >> b[i];
    }
    brute(1);
    cout << "NO" << '\n';
  }
}

namespace sub_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';
  }
}

signed main() {
  cin >> n >> m;
  if (n == 1 && m <= 20) sub_1::solve();
  else if (n <= 10 && m <= 10) sub_2::solve();
  else if (n <= 20 && m <= 14) sub_3::solve();
}

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