제출 #1325502

#제출 시각아이디문제언어결과실행 시간메모리
1325502fr1tzy은행 (IZhO14_bank)C++20
0 / 100
0 ms568 KiB
#include <bits/stdc++.h>
using namespace std;
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n, m;
  cin >> n >> m;
  vector<int> a(n), b(m);
  for (int i = 0; i < n; i++)
    cin >> a[i];
  for (int i = 0; i < m; i++)
    cin >> b[i];
  sort(a.begin(), a.end(), greater<int>());
  long long total = 0;
  for (int x : a)
    total += x;
  vector<long long> p(m + 1, 0);
  for (int i = 0; i < n; i++)
    p[i + 1] = p[i] + a[i];

  int s = 1 << m;
  vector<long long> c(s, 0);
  for (int ma = 1; ma < s; ma++) {
    int l = ma & -ma;
    int id = __builtin_ctz(l);
    c[ma] = c[ma ^ l] + b[id];
  }
  vector<char> dp(s, 0);
  dp[0] = 1;
  for (int ma = 1; ma < s; ma++) {
    if (!dp[ma])
      continue;
    long long u = c[ma];
    if (u == total) {
      cout << "YES\n";
      return 0;
    }
    int k = int(upper_bound(p.begin(), p.end(), u) - p.begin()) - 1;
    if (k >= n) {
      cout << "YES\n";
      return 0;
    }
    long long r = u - p[k];
    if (r > a[k])
      continue;
    for (int i = 0; i < m; i++) {
      if (ma & (1 << i))
        continue;
      long long next = u + b[i];
      if (next > total)
        continue;
      if (r + b[i] <= a[k]) {
        dp[ma | (1 << i)] = 1;
      }
    }
  }
  cout << "NO\n";
  return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...