제출 #1286178

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1286178		OmarAlimammadzade	은행 (IZhO14_bank)	C++20	19 / 100	86 ms	16828 KiB

bank

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

#ifdef LOCAL
#include "algo/debug"
#else
#define dbg(...)
#endif

#define int long long

void run() {
  int n, m;
  cin >> n >> m;
  int a[n + 1], b[m + 1];
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  for (int i = 1; i <= m; i++) {
    cin >> b[i];
  }
  int sum[1 << m];
  fill(sum, sum + (1 << m), 0);
  for (int msk = 0; msk < 1 << m; msk++) {
    for (int i = 0; i < m; i++) {
      sum[msk] += (msk >> i & 1) * b[i + 1];
    }
  }
  int pref[n + 1];
  pref[0] = 0;
  for (int i = 1; i <= n; i++) {
    pref[i] = pref[i - 1] + a[i];
  }
  int dp[1 << m];
  fill(dp, dp + (1 << m), 0);
  for (int msk = 0; msk < 1 << m; msk++) {
    for (int i = 0; i < m; i++) {
      if (msk >> i & 1) {
        continue;
      }
      int nw_msk = 1 << i | msk;
      if (sum[msk] - pref[dp[msk]] + b[i + 1] == a[dp[msk] + 1]) {
        dp[nw_msk] = max(dp[nw_msk], dp[msk] + 1);
      }
    }
  }
  for (int msk = 0; msk < 1 << m; msk++) {
    if (dp[msk] == n) {
      cout << "YES\n";
      return;
    }
  }
  cout << "NO\n";
}

signed main() {
  ios::sync_with_stdio(0);
  cin.tie(nullptr);
  int tt = 1;
  // cin >> tt;
  while (tt--) {
    run();
  }
}

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