제출 #1286182

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1286182		OmarAlimammadzade	은행 (IZhO14_bank)	C++20	100 / 100	101 ms	16848 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], b[m];
  for (int &i : a) {
    cin >> i;
  }
  for (int &i : b) {
    cin >> i;
  }
  int extra[1 << m], dp[1 << m];
  fill(extra, extra + (1 << m), -1);
  fill(dp, dp + (1 << m), -1);
  dp[0] = extra[0] = 0;
  for (int msk = 0; msk < 1 << m; msk++) {
    for (int i = 0; i < m; i++) {
      if (!(msk >> i & 1)) {
        continue;
      }
      int prev = 1 << i ^ msk;
      if (dp[prev] == -1) {
        continue;
      }
      if (extra[prev] + b[i] < a[dp[prev]]) {
        extra[msk] = extra[prev] + b[i];
        dp[msk] = dp[prev];
      } else if (extra[prev] + b[i] == a[dp[prev]]) {
        extra[msk] = 0;
        dp[msk] = dp[prev] + 1;
      }
    }
    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: 25 / 25
• Subtask 3: 27 / 27
• Subtask 4: 29 / 29