#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include int main() { constexpr int MAX_K = 100000; constexpr int SEGMENT = 100; int n, k; std::cin >> n >> k; std::vector number(n); for (auto& a : number) { std::cin >> a; } std::vector> forward_memo((n + SEGMENT - 1) / SEGMENT); std::bitset forward; forward.set(0, true); for (auto i = 0; i < n; ++i) { if (i % SEGMENT == 0) { forward_memo[i / SEGMENT] = forward; } forward |= forward << number[i]; } if (forward.test(k)) { int result{ 0 }; std::bitset backward; backward.set(k, true); std::vector> forward_cache; forward_cache.reserve(SEGMENT); for (int i = n - 1; i >= 0; --i) { if (forward_cache.empty()) { const auto from = i / SEGMENT * SEGMENT; const auto until = std::min(n, from + SEGMENT); forward_cache.push_back(forward_memo[i / SEGMENT]); for (auto j = from + 1; j < until; ++j) { forward_cache.push_back(forward_cache.back() | (forward_cache.back() << number[j - 1])); } } const auto a = number[i]; if ((backward & forward_cache.back()).none()) { result += 1; } backward |= backward >> a; forward_cache.pop_back(); } std::cout << result << '\n'; } else { std::cout << "-1\n"; } }