제출 #891671

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
891671		ind1v	은행 (IZhO14_bank)	C++11	71 / 100	14 ms	14428 KiB

bank

#include <bits/stdc++.h>

using namespace std;

int n, m;
vector<int> a, b;

namespace sub1 {
  bool check() {
    return n == 1 && m <= 20;
  }
  
  void solve() {
    bool f = false;
    for (int msk = 0; msk < (1 << m); msk++) {
      int tot = 0;
      for (int i = 0; i < m; i++) {
        tot += (msk >> i & 1) * b[i];
      }
      f |= (tot == a[0]);
    }
    cout << (f ? "YES" : "NO") << '\n';
  }
}

namespace sub2 {
  bool check() {
    return n <= 10 && m <= 10;
  }
  
  int w[1 << 10];
  int f[10][1 << 10];
  
  int dp(int id, int msk) {
    if (id == -1) {
      return true;
    }
    int &res = f[id][msk];
    if (res != -1) {
      return res;
    }
    res = 0;
    for (int sm = 0; sm < (1 << m); sm++) {
      if (w[sm] == a[id] && ((msk & sm) == sm)) {
        res |= dp(id - 1, msk ^ sm);
      }
    }
    return res;
  }
  
  void solve() {
    memset(w, 0, sizeof(w));
    for (int msk = 0; msk < (1 << m); msk++) {
      for (int i = 0; i < m; i++) {
        w[msk] += (msk >> i & 1) * b[i];
      }
    }
    memset(f, -1, sizeof(f));
    cout << (dp(n - 1, (1 << m) - 1) ? "YES" : "NO") << '\n';
  }
}

namespace sub3 {
  bool check() {
    return n <= 20 && m <= 14;
  }
  
  int w[1 << 14];
  int f[14][1 << 14];
  
  int dp(int id, int msk) {
    if (id == -1) {
      return true;
    }
    int &res = f[id][msk];
    if (res != -1) {
      return res;
    }
    res = 0;
    for (int sm = msk; !res; sm = (sm - 1) & msk) {
      if (w[sm] == a[id]) {
        res |= dp(id - 1, msk ^ sm);
      }
      if (sm == 0) {
        break;
      }
    }
    return res;
  }
  
  void solve() {
    if (n > m) {
      cout << "NO";
      return;
    }
    memset(w, 0, sizeof(w));
    for (int msk = 0; msk < (1 << m); msk++) {
      for (int i = 0; i < m; i++) {
        w[msk] += (msk >> i & 1) * b[i];
      }
    }
    memset(f, -1, sizeof(f));
    cout << (dp(n - 1, (1 << m) - 1) ? "YES": "NO") << '\n';
  }
}

namespace sub4 {
  bool check() {
    return n <= 20 && m <= 20;
  }
  
  int w[1 << 20];
  vector<int> mv[1005];
  int f[20][1 << 20];
  
  int dp(int id, int msk) {
    if (id == -1) {
      return true;
    }
    int &res = f[id][msk];
    if (res != -1) {
      return res;
    }
    res = 0;
    for (int i = 0; i < (int) mv[a[id]].size() && !res; i++) {
      if ((msk & mv[a[id]][i]) == mv[a[id]][i]) {
        res |= dp(id - 1, msk ^ mv[a[id]][i]);
      }
    }
    return res;
  }
  
  void solve() {
    if (n > m) {
      cout << "NO";
      return;
    }
    memset(w, 0, sizeof(w));
    for (int msk = 0; msk < (1 << m); msk++) {
      for (int i = 0; i < m; i++) {
        w[msk] += (msk >> i & 1) * b[i];
      }
      mv[w[msk]].emplace_back(msk);
    }
    memset(f, -1, sizeof(f));
    cout << (dp(n - 1, (1 << m) - 1) ? "YES": "NO") << '\n';
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n >> m;
  a.resize(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  b.resize(m);
  for (int i = 0; i < m; i++) {
    cin >> b[i];
  }
  if (sub1::check()) {
    sub1::solve();
    exit(0);
  }
  if (sub2::check()) {
    sub2::solve();
    exit(0);
  }
  if (sub3::check()) {
    sub3::solve();
    exit(0);
  }
  if (sub4::check()) {
    sub4::solve();
    exit(0);
  }
  return 0;
}

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