Submission #1184744

#	Time	Username	Problem	Language	Result	Execution time	Memory
1184744		versesrev	Bank (IZhO14_bank)	C++20	Compilation error	0 ms	0 KiB

bank

#include <iostream>
#include <array>
#include <map>
#include <algorithm>
#include <vector>
#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::vector<std::vector<int>> dp(m, std::vector<int>(as[0] + 1));
  for (int i = 0; i < m; ++i) {
    for (int j = 0; j <= as[0]; ++j) {
      if (i == 0) dp[i][j] = j == 0 or j == bs[i];
      else {
        dp[i][j] = dp[i - 1][j];
        if (bs[i] <= j) dp[i][j] += dp[i - 1][j - bs[i]];
      }
    }
  }
  
  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 {
    /*
    std::cout << "brute a_sum=" << a_sum << " b_sum=" << b_sum
              << " " << state[0]
              << " " << state[19] << " " << state[20] << "\n";
    // */
    if (table.contains(state)) return table[state];
    assert(b_sum == std::accumulate(bs.begin() + state[0], bs.end(), 0));
    assert(a_sum == std::accumulate(state.begin() + 1, state.end()));
    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];
    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;
    }
    if (self(self, new_state, a_sum, b_sum - b)) {
      return table[state] = true;
    }
    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 << (ans ? "YES\n" : "NO\n");
}

Compilation message (stderr)

bank.cpp: In lambda function:
bank.cpp:36:5: error: there are no arguments to 'assert' that depend on a template parameter, so a declaration of 'assert' must be available [-fpermissive]
   36 |     assert(b_sum == std::accumulate(bs.begin() + state[0], bs.end(), 0));
      |     ^~~~~~
bank.cpp:36:5: note: (if you use '-fpermissive', G++ will accept your code, but allowing the use of an undeclared name is deprecated)
bank.cpp:37:36: error: no matching function for call to 'accumulate(std::array<int, 21>::const_iterator, std::array<int, 21>::const_iterator)'
   37 |     assert(a_sum == std::accumulate(state.begin() + 1, state.end()));
      |                     ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/numeric:62,
                 from bank.cpp:6:
/usr/include/c++/11/bits/stl_numeric.h:134:5: note: candidate: 'template<class _InputIterator, class _Tp> constexpr _Tp std::accumulate(_InputIterator, _InputIterator, _Tp)'
  134 |     accumulate(_InputIterator __first, _InputIterator __last, _Tp __init)
      |     ^~~~~~~~~~
/usr/include/c++/11/bits/stl_numeric.h:134:5: note:   template argument deduction/substitution failed:
bank.cpp:37:36: note:   candidate expects 3 arguments, 2 provided
   37 |     assert(a_sum == std::accumulate(state.begin() + 1, state.end()));
      |                     ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/numeric:62,
                 from bank.cpp:6:
/usr/include/c++/11/bits/stl_numeric.h:161:5: note: candidate: 'template<class _InputIterator, class _Tp, class _BinaryOperation> constexpr _Tp std::accumulate(_InputIterator, _InputIterator, _Tp, _BinaryOperation)'
  161 |     accumulate(_InputIterator __first, _InputIterator __last, _Tp __init,
      |     ^~~~~~~~~~
/usr/include/c++/11/bits/stl_numeric.h:161:5: note:   template argument deduction/substitution failed:
bank.cpp:37:36: note:   candidate expects 4 arguments, 2 provided
   37 |     assert(a_sum == std::accumulate(state.begin() + 1, state.end()));
      |                     ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bank.cpp:37:5: error: there are no arguments to 'assert' that depend on a template parameter, so a declaration of 'assert' must be available [-fpermissive]
   37 |     assert(a_sum == std::accumulate(state.begin() + 1, state.end()));
      |     ^~~~~~
bank.cpp: In instantiation of 'main()::<lambda(auto:16&&, const std::array<int, 21>&, int, int)> [with auto:16 = main()::<lambda(auto:16&&, const std::array<int, 21>&, int, int)>&]':
bank.cpp:70:19:   required from here
bank.cpp:36:11: error: 'assert' was not declared in this scope
   36 |     assert(b_sum == std::accumulate(bs.begin() + state[0], bs.end(), 0));
      |     ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bank.cpp:7:1: note: 'assert' is defined in header '<cassert>'; did you forget to '#include <cassert>'?
    6 | #include <numeric>
  +++ |+#include <cassert>
    7 | 
bank.cpp:37:68: error: 'assert' was not declared in this scope, and no declarations were found by argument-dependent lookup at the point of instantiation
   37 |     assert(a_sum == std::accumulate(state.begin() + 1, state.end()));
      |                                                                    ^