제출 #1325511

#제출 시각아이디문제언어결과실행 시간메모리
1325511fr1tzy은행 (IZhO14_bank)C++20
100 / 100
77 ms9608 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(N + 1, 0);
  for (int i = 0; i < N; i++)
    p[i + 1] = p[i] + a[i];
  int s = 1 << M;
  vector<long long> sum(s, 0);
  for (int mask = 1; mask < s; mask++) {
    int l = mask & -mask;
    int id = __builtin_ctz(l);
    sum[mask] = sum[mask ^ l] + b[id];
  }
  vector<char> dp(s, 0);
  dp[0] = 1;
  for (int mask = 0; mask < s; mask++) {
    if (!dp[mask])
      continue;
    long long used = sum[mask];
    if (used > total)
      continue;

    if (used == total) {
      cout << "YES\n";
      return 0;
    }
    int k = int(upper_bound(p.begin(), p.end(), used) - p.begin()) - 1;
    if (k >= N) {
      cout << "YES\n";
      return 0;
    }
    long long r = used - p[k];
    if (r > a[k])
      continue;
    for (int i = 0; i < M; i++) {
      if (mask & (1 << i))
        continue;
      long long next = used + b[i];
      if (next > total)
        continue;
      if (r + b[i] <= a[k]) {
        dp[mask | (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...