제출 #1184727

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1184727		versesrev	Bank (IZhO14_bank)	C++20	0 / 100	1100 ms	143296 KiB

bank

#include <iostream>
#include <array>
#include <map>
#include <algorithm>
#include <numeric>

int main() {
  int n, m;
  std::cin >> n >> m;
  std::vector<int> as(n), bs(m);
  for (int& a : as) std::cin >> a;
  for (int& b : bs) std::cin >> b;
  
  std::ranges::sort(as), std::ranges::sort(bs);
  
  std::map<std::array<int, 21>, bool> table;
  auto brute = [&](auto&& self, const std::array<int, 21>& state, int a_sum, int b_sum) -> bool {
    if (table.contains(state)) return table[state];
    if (b_sum < a_sum) {
      return table[state] = false;
    }
    if (state[0] == m) {
      return table[state] = (a_sum == 0);
    }
    std::array<int, 21> new_state = state;
    int b = bs[new_state[0]]; ++new_state[0];
    if (self(self, new_state, a_sum, b_sum - b)) {
      return table[state] = true;
    }
    for (int i = 1; i < 21; ++i) {
      if (b < new_state[i]) continue;
      new_state[i] -= b;
      int j = i;
      for (; j > 1 and new_state[j-1] > new_state[j]; --j) {
        std::swap(new_state[j-1], new_state[j]);
      }
      if (self(self, new_state, a_sum - b, b_sum - b)) { return table[state] = true; }
      for (; j != i; ++j) {
        std::swap(new_state[j+1], new_state[j]);
      }
      new_state[i] += b;
    }
    return table[state] = false;
  };
  
  std::array<int, 21> state;
  for (int i = 0; i < n; ++i) state[i] = as[i];
  std::ranges::sort(state);
  int a_sum = std::accumulate(as.begin(), as.end(), 0);
  int b_sum = std::accumulate(bs.begin(), bs.end(), 0);
  bool ans = brute(brute, state, a_sum, b_sum);
  std::cout << "YES\n";
}

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