tests/zero_one_knapsack/solve_by_dp_maximizing_value.test.cpp

• View this file on GitHub
• Last update: 2025-02-10 01:30:13+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/problems/DPL_1_B

Depends on

• Assertion macro (tools/assert_that.hpp)
• $\left\lceil \frac{x}{y} \right\rceil$ (tools/ceil.hpp)
• chmax function (tools/chmax.hpp)
• chmin function (tools/chmin.hpp)
• std::is_integral extended for tools::int128_t and tools::uint128_t (tools/is_integral.hpp)
• std::is_unsigned extended for tools::int128_t and tools::uint128_t (tools/is_unsigned.hpp)
• std::less by std::get (tools/less_by_get.hpp)
• $2^x$ (tools/pow2.hpp)
• $\mathbb{Z} \cup \{\infty, -\infty, \mathrm{NaN}\}$ and $\mathbb{Z}_{\geq 0} \cup \{\infty, \mathrm{NaN}\}$ (tools/safe_int.hpp)
• 0-1 knapsack problem (tools/zero_one_knapsack.hpp)

Code

// competitive-verifier: PROBLEM https://onlinejudge.u-aizu.ac.jp/problems/DPL_1_B

#include <iostream>
#include "tools/zero_one_knapsack.hpp"
#include "tools/assert_that.hpp"

using ll = long long;

int main() {
  std::cin.tie(nullptr);
  std::ios_base::sync_with_stdio(false);

  ll N, W;
  std::cin >> N >> W;
  tools::zero_one_knapsack<ll> solver(W);
  for (ll i = 0; i < N; ++i) {
    ll v, w;
    std::cin >> v >> w;
    solver.add_item(v, w);
  }

  const auto [answer, selected] = solver.query();
  ll v = 0;
  ll w = 0;
  for (const auto i : selected) {
    v += solver.get_item(i).first;
    w += solver.get_item(i).second;
  }
  assert_that(v == answer);
  assert_that(w <= W);
  std::cout << answer << '\n';

  return 0;
}

#line 1 "tests/zero_one_knapsack/solve_by_dp_maximizing_value.test.cpp"
// competitive-verifier: PROBLEM https://onlinejudge.u-aizu.ac.jp/problems/DPL_1_B

#include <iostream>
#line 1 "tools/zero_one_knapsack.hpp"



#include <vector>
#include <utility>
#include <cassert>
#include <cstddef>
#include <limits>
#include <iterator>
#include <algorithm>
#include <tuple>
#include <array>
#include <numeric>
#line 1 "tools/chmax.hpp"



#include <type_traits>
#line 6 "tools/chmax.hpp"

namespace tools {

  template <typename M, typename N>
  bool chmax(M& lhs, const N& rhs) {
    bool updated;
    if constexpr (::std::is_integral_v<M> && ::std::is_integral_v<N>) {
      updated = ::std::cmp_less(lhs, rhs);
    } else {
      updated = lhs < rhs;
    }
    if (updated) lhs = rhs;
    return updated;
  }
}


#line 1 "tools/chmin.hpp"



#line 6 "tools/chmin.hpp"

namespace tools {

  template <typename M, typename N>
  bool chmin(M& lhs, const N& rhs) {
    bool updated;
    if constexpr (::std::is_integral_v<M> && ::std::is_integral_v<N>) {
      updated = ::std::cmp_less(rhs, lhs);
    } else {
      updated = rhs < lhs;
    }
    if (updated) lhs = rhs;
    return updated;
  }
}


#line 1 "tools/less_by_get.hpp"



#line 6 "tools/less_by_get.hpp"

namespace tools {

  template <::std::size_t I>
  struct less_by_get {
    template <class T>
    bool operator()(const T& x, const T& y) const {
      return ::std::get<I>(x) < ::std::get<I>(y);
    }
  };
}


#line 1 "tools/safe_int.hpp"



#line 9 "tools/safe_int.hpp"
#include <optional>
#line 11 "tools/safe_int.hpp"

namespace tools {
  template <typename T, typename = void>
  class safe_int;

  template <typename T>
  class safe_int<T, ::std::enable_if_t<::std::is_signed_v<T>>> {
  private:
    enum class type {
      finite,
      pos_inf,
      neg_inf,
      nan
    };
    typename ::tools::safe_int<T>::type m_type;
    T m_value;

    constexpr safe_int(const typename ::tools::safe_int<T>::type type) :
      m_type(type), m_value(T()) {
    }

  public:
    constexpr safe_int() :
      m_type(::tools::safe_int<T>::type::finite), m_value(T()) {
    }
    explicit constexpr safe_int(const T value) :
      m_type(::tools::safe_int<T>::type::finite), m_value(value) {
    }
    constexpr safe_int(const ::tools::safe_int<T>& other) :
      m_type(other.m_type), m_value(other.m_value) {
    }
    ~safe_int() = default;
    constexpr ::tools::safe_int<T>& operator=(const ::tools::safe_int<T>& other) {
      this->m_type = other.m_type;
      this->m_value = other.m_value;
      return *this;
    }

    static constexpr ::tools::safe_int<T> infinity() {
      return tools::safe_int<T>(::tools::safe_int<T>::type::pos_inf);
    }
    static constexpr ::tools::safe_int<T> nan() {
      return tools::safe_int<T>(::tools::safe_int<T>::type::nan);
    }

  private:
    static constexpr int f1(const ::tools::safe_int<T>& n) {
      switch (n.m_type) {
      case ::tools::safe_int<T>::type::neg_inf:
        return 0;
      case ::tools::safe_int<T>::type::finite:
        return 1;
      case ::tools::safe_int<T>::type::pos_inf:
        return 2;
      default: // nan
        return 3;
      }
    };
    static constexpr int f2(const ::tools::safe_int<T>& n) {
      switch (n.m_type) {
      case ::tools::safe_int<T>::type::neg_inf:
        return 0;
      case ::tools::safe_int<T>::type::finite:
        if (n.m_value < 0) {
          return 1;
        } else if (n.m_value == 0) {
          return 2;
        } else {
          return 3;
        }
      case ::tools::safe_int<T>::type::pos_inf:
        return 4;
      default: // nan
        return 5;
      }
    };
    static constexpr ::std::optional<::tools::safe_int<T>> Q() {
      return ::std::nullopt;
    }
    static constexpr ::std::optional<::tools::safe_int<T>> Z() {
      return ::std::optional<::tools::safe_int<T>>(::tools::safe_int<T>(0));
    }
    static constexpr ::std::optional<::tools::safe_int<T>> N() {
      return ::std::optional<::tools::safe_int<T>>(::tools::safe_int<T>(::tools::safe_int<T>::type::neg_inf));
    }
    static constexpr ::std::optional<::tools::safe_int<T>> P() {
      return ::std::optional<::tools::safe_int<T>>(::tools::safe_int<T>(::tools::safe_int<T>::type::pos_inf));
    }
    static constexpr ::std::optional<::tools::safe_int<T>> U() {
      return ::std::optional<::tools::safe_int<T>>(::tools::safe_int<T>(::tools::safe_int<T>::type::nan));
    }
    static constexpr ::std::optional<bool> BQ() {
      return ::std::nullopt;
    }
    static constexpr ::std::optional<bool> BF() {
      return ::std::optional<bool>(false);
    }
    static constexpr ::std::optional<bool> BT() {
      return ::std::optional<bool>(true);
    }

  public:
    constexpr bool is_finite() const {
      return this->m_type == ::tools::safe_int<T>::type::finite;
    }

    constexpr bool is_nan() const {
      return this->m_type == ::tools::safe_int<T>::type::nan;
    }

    constexpr T val() const {
      assert(this->is_finite());
      return this->m_value;
    }

    friend constexpr bool operator==(const ::tools::safe_int<T>& x, const ::tools::safe_int<T>& y) {
      constexpr auto table = ::std::array<::std::array<::std::optional<bool>, 4>, 4>({{
        {BT(), BF(), BF(), BF()},
        {BF(), BQ(), BF(), BF()},
        {BF(), BF(), BT(), BF()},
        {BF(), BF(), BF(), BF()}
      }});
      if (const auto r = table[f1(x)][f1(y)]; r) return *r;

      return x.m_value == y.m_value;
    }
    friend constexpr bool operator!=(const ::tools::safe_int<T>& x, const ::tools::safe_int<T>& y) {
      return !(x == y);
    }

    constexpr ::tools::safe_int<T> operator+() const {
      return *this;
    }
    constexpr ::tools::safe_int<T> operator-() const {
      constexpr auto table = ::std::array<::std::optional<::tools::safe_int<T>>, 4>({
        {P(), Q(), N(), U()}
      });
      if (const auto r = table[f1(*this)]; r) return *r;

      if (this->m_value == ::std::numeric_limits<T>::min()) return *U();
      return ::tools::safe_int<T>(-this->m_value);
    }

    friend constexpr ::tools::safe_int<T> operator+(const ::tools::safe_int<T>& x, const ::tools::safe_int<T>& y) {
      constexpr auto table = ::std::array<::std::array<::std::optional<::tools::safe_int<T>>, 4>, 4>({{
        {N(), N(), U(), U()},
        {N(), Q(), P(), U()},
        {U(), P(), P(), U()},
        {U(), U(), U(), U()}
      }});
      if (const auto r = table[f1(x)][f1(y)]; r) return *r;

      if (y.m_value > 0 && x.m_value > ::std::numeric_limits<T>::max() - y.m_value) return *U();
      if (y.m_value < 0 && x.m_value < ::std::numeric_limits<T>::min() - y.m_value) return *U();
      return ::tools::safe_int<T>(x.m_value + y.m_value);
    }
    friend constexpr ::tools::safe_int<T> operator+(const ::tools::safe_int<T>& x, const T& y) {
      return x + tools::safe_int<T>(y);
    }
    friend constexpr ::tools::safe_int<T> operator+(const T& x, const ::tools::safe_int<T>& y) {
      return tools::safe_int<T>(x) + y;
    }

    friend constexpr ::tools::safe_int<T> operator-(const ::tools::safe_int<T>& x, const ::tools::safe_int<T>& y) {
      constexpr auto table = ::std::array<::std::array<::std::optional<::tools::safe_int<T>>, 4>, 4>({{
        {U(), N(), N(), U()},
        {P(), Q(), N(), U()},
        {P(), P(), U(), U()},
        {U(), U(), U(), U()}
      }});
      if (const auto r = table[f1(x)][f1(y)]; r) return *r;

      if (y.m_value < 0 && x.m_value > ::std::numeric_limits<T>::max() + y.m_value) return *U();
      if (y.m_value > 0 && x.m_value < ::std::numeric_limits<T>::min() + y.m_value) return *U();
      return ::tools::safe_int<T>(x.m_value - y.m_value);
    }
    friend constexpr ::tools::safe_int<T> operator-(const ::tools::safe_int<T>& x, const T& y) {
      return x - tools::safe_int<T>(y);
    }
    friend constexpr ::tools::safe_int<T> operator-(const T& x, const ::tools::safe_int<T>& y) {
      return tools::safe_int<T>(x) - y;
    }

    friend constexpr ::tools::safe_int<T> operator*(const ::tools::safe_int<T>& x, const ::tools::safe_int<T>& y) {
      constexpr auto table = ::std::array<::std::array<::std::optional<::tools::safe_int<T>>, 6>, 6>({{
        {P(), P(), U(), N(), N(), U()},
        {P(), Q(), Z(), Q(), N(), U()},
        {U(), Z(), Z(), Z(), U(), U()},
        {N(), Q(), Z(), Q(), P(), U()},
        {N(), N(), U(), P(), P(), U()},
        {U(), U(), U(), U(), U(), U()}
      }});
      if (const auto r = table[f2(x)][f2(y)]; r) return *r;

      if (x.m_value > 0) {
        if (y.m_value > 0) {
          if (x.m_value > ::std::numeric_limits<T>::max() / y.m_value) {
            return *U();
          }
        } else {
          if (y.m_value < ::std::numeric_limits<T>::min() / x.m_value) {
            return *U();
          }
        }
      } else {
        if (y.m_value > 0) {
          if (x.m_value < ::std::numeric_limits<T>::min() / y.m_value) {
            return *U();
          }
        } else {
          if (x.m_value != 0 && y.m_value < ::std::numeric_limits<T>::max() / x.m_value) {
            return *U();
          }
        }
      }
      return ::tools::safe_int<T>(x.m_value * y.m_value);
    }
    friend constexpr ::tools::safe_int<T> operator*(const ::tools::safe_int<T>& x, const T& y) {
      return x * tools::safe_int<T>(y);
    }
    friend constexpr ::tools::safe_int<T> operator*(const T& x, const ::tools::safe_int<T>& y) {
      return tools::safe_int<T>(x) * y;
    }

    friend constexpr ::tools::safe_int<T> operator/(const ::tools::safe_int<T>& x, const ::tools::safe_int<T>& y) {
      constexpr auto table = ::std::array<::std::array<::std::optional<::tools::safe_int<T>>, 6>, 6>({{
        {U(), P(), U(), N(), U(), U()},
        {Z(), Q(), U(), Q(), Z(), U()},
        {Z(), Z(), U(), Z(), Z(), U()},
        {Z(), Q(), U(), Q(), Z(), U()},
        {U(), N(), U(), P(), U(), U()},
        {U(), U(), U(), U(), U(), U()}
      }});
      if (const auto r = table[f2(x)][f2(y)]; r) return *r;

      if (x.m_value == ::std::numeric_limits<T>::min() && y.m_value == -1) return *U();
      return ::tools::safe_int<T>(x.m_value / y.m_value);
    }
    friend constexpr ::tools::safe_int<T> operator/(const ::tools::safe_int<T>& x, const T& y) {
      return x / tools::safe_int<T>(y);
    }
    friend constexpr ::tools::safe_int<T> operator/(const T& x, const ::tools::safe_int<T>& y) {
      return tools::safe_int<T>(x) / y;
    }

    friend constexpr ::tools::safe_int<T> operator%(const ::tools::safe_int<T>& x, const ::tools::safe_int<T>& y) {
      constexpr auto table = ::std::array<::std::array<::std::optional<::tools::safe_int<T>>, 6>, 6>({{
        {U(), U(), U(), U(), U(), U()},
        {U(), Q(), U(), Q(), U(), U()},
        {U(), Z(), U(), Z(), U(), U()},
        {U(), Q(), U(), Q(), U(), U()},
        {U(), U(), U(), U(), U(), U()},
        {U(), U(), U(), U(), U(), U()}
      }});
      if (const auto r = table[f2(x)][f2(y)]; r) return *r;

      if (x.m_value == ::std::numeric_limits<T>::min() && y.m_value == -1) return *U();
      return ::tools::safe_int<T>(x.m_value % y.m_value);
    }
    friend constexpr ::tools::safe_int<T> operator%(const ::tools::safe_int<T>& x, const T& y) {
      return x % tools::safe_int<T>(y);
    }
    friend constexpr ::tools::safe_int<T> operator%(const T& x, const ::tools::safe_int<T>& y) {
      return tools::safe_int<T>(x) % y;
    }

    constexpr ::tools::safe_int<T>& operator+=(const ::tools::safe_int<T>& other) {
      return *this = *this + other;
    }
    constexpr ::tools::safe_int<T>& operator+=(const T& other) {
      return *this = *this + ::tools::safe_int<T>(other);
    }
    constexpr ::tools::safe_int<T>& operator-=(const ::tools::safe_int<T>& other) {
      return *this = *this - other;
    }
    constexpr ::tools::safe_int<T>& operator-=(const T& other) {
      return *this = *this - ::tools::safe_int<T>(other);
    }
    constexpr ::tools::safe_int<T>& operator*=(const ::tools::safe_int<T>& other) {
      return *this = *this * other;
    }
    constexpr ::tools::safe_int<T>& operator*=(const T& other) {
      return *this = *this * ::tools::safe_int<T>(other);
    }
    constexpr ::tools::safe_int<T>& operator/=(const ::tools::safe_int<T>& other) {
      return *this = *this / other;
    }
    constexpr ::tools::safe_int<T>& operator/=(const T& other) {
      return *this = *this / ::tools::safe_int<T>(other);
    }
    constexpr ::tools::safe_int<T>& operator%=(const ::tools::safe_int<T>& other) {
      return *this = *this % other;
    }
    constexpr ::tools::safe_int<T>& operator%=(const T& other) {
      return *this = *this % ::tools::safe_int<T>(other);
    }

    constexpr ::tools::safe_int<T>& operator++() {
      return *this += ::tools::safe_int<T>(T(1));
    }
    constexpr ::tools::safe_int<T> operator++(int) {
      const auto r = *this;
      ++(*this);
      return r;
    }
    constexpr ::tools::safe_int<T>& operator--() {
      return *this -= ::tools::safe_int<T>(T(1));
    }
    constexpr ::tools::safe_int<T> operator--(int) {
      const auto r = *this;
      --(*this);
      return r;
    }

    friend constexpr bool operator<(const ::tools::safe_int<T>& x, const ::tools::safe_int<T>& y) {
      constexpr auto table = ::std::array<::std::array<::std::optional<bool>, 4>, 4>({{
        {BF(), BT(), BT(), BF()},
        {BF(), BQ(), BT(), BF()},
        {BF(), BF(), BF(), BF()},
        {BF(), BF(), BF(), BF()}
      }});
      if (const auto r = table[f1(x)][f1(y)]; r) return *r;

      return x.m_value < y.m_value;
    }
    friend constexpr bool operator>(const ::tools::safe_int<T>& x, const ::tools::safe_int<T>& y) {
      constexpr auto table = ::std::array<::std::array<::std::optional<bool>, 4>, 4>({{
        {BF(), BF(), BF(), BF()},
        {BT(), BQ(), BF(), BF()},
        {BT(), BT(), BF(), BF()},
        {BF(), BF(), BF(), BF()}
      }});
      if (const auto r = table[f1(x)][f1(y)]; r) return *r;

      return x.m_value > y.m_value;
    }
    friend constexpr bool operator<=(const ::tools::safe_int<T>& x, const ::tools::safe_int<T>& y) {
      return x < y || x == y;
    }
    friend constexpr bool operator>=(const ::tools::safe_int<T>& x, const ::tools::safe_int<T>& y) {
      return x > y || x == y;
    }

    friend ::std::istream& operator>>(::std::istream& is, ::tools::safe_int<T>& self) {
      self.m_type = ::tools::safe_int<T>::type::finite;
      return is >> self.m_value;
    }
    friend ::std::ostream& operator<<(::std::ostream& os, const ::tools::safe_int<T>& self) {
      switch (self.m_type) {
      case ::tools::safe_int<T>::type::neg_inf:
        return os << "-inf";
      case ::tools::safe_int<T>::type::finite:
        return os << self.m_value;
      case ::tools::safe_int<T>::type::pos_inf:
        return os << "inf";
      default: // nan
        return os << "nan";
      }
    }
  };

  template <typename T>
  class safe_int<T, ::std::enable_if_t<::std::is_unsigned_v<T>>> {
  private:
    enum class type {
      finite,
      pos_inf,
      nan
    };
    typename ::tools::safe_int<T>::type m_type;
    T m_value;

    constexpr safe_int(const typename ::tools::safe_int<T>::type type) :
      m_type(type), m_value(T()) {
    }

  public:
    constexpr safe_int() :
      m_type(::tools::safe_int<T>::type::finite), m_value(T()) {
    }
    explicit constexpr safe_int(const T value) :
      m_type(::tools::safe_int<T>::type::finite), m_value(value) {
    }
    constexpr safe_int(const ::tools::safe_int<T>& other) :
      m_type(other.m_type), m_value(other.m_value) {
    }
    ~safe_int() = default;
    constexpr ::tools::safe_int<T>& operator=(const ::tools::safe_int<T>& other) {
      this->m_type = other.m_type;
      this->m_value = other.m_value;
      return *this;
    }

    static constexpr ::tools::safe_int<T> infinity() {
      return tools::safe_int<T>(::tools::safe_int<T>::type::pos_inf);
    }
    static constexpr ::tools::safe_int<T> nan() {
      return tools::safe_int<T>(::tools::safe_int<T>::type::nan);
    }

  private:
    static constexpr int f1(const ::tools::safe_int<T>& n) {
      switch (n.m_type) {
      case ::tools::safe_int<T>::type::finite:
        return 0;
      case ::tools::safe_int<T>::type::pos_inf:
        return 1;
      default: // nan
        return 2;
      }
    };
    static constexpr int f2(const ::tools::safe_int<T>& n) {
      switch (n.m_type) {
      case ::tools::safe_int<T>::type::finite:
        if (n.m_value == 0) {
          return 0;
        } else {
          return 1;
        }
      case ::tools::safe_int<T>::type::pos_inf:
        return 2;
      default: // nan
        return 3;
      }
    };
    static constexpr ::std::optional<::tools::safe_int<T>> Q() {
      return ::std::nullopt;
    }
    static constexpr ::std::optional<::tools::safe_int<T>> Z() {
      return ::std::optional<::tools::safe_int<T>>(::tools::safe_int<T>(0));
    }
    static constexpr ::std::optional<::tools::safe_int<T>> P() {
      return ::std::optional<::tools::safe_int<T>>(::tools::safe_int<T>(::tools::safe_int<T>::type::pos_inf));
    }
    static constexpr ::std::optional<::tools::safe_int<T>> U() {
      return ::std::optional<::tools::safe_int<T>>(::tools::safe_int<T>(::tools::safe_int<T>::type::nan));
    }
    static constexpr ::std::optional<bool> BQ() {
      return ::std::nullopt;
    }
    static constexpr ::std::optional<bool> BF() {
      return ::std::optional<bool>(false);
    }
    static constexpr ::std::optional<bool> BT() {
      return ::std::optional<bool>(true);
    }

  public:
    constexpr bool is_finite() const {
      return this->m_type == ::tools::safe_int<T>::type::finite;
    }

    constexpr bool is_nan() const {
      return this->m_type == ::tools::safe_int<T>::type::nan;
    }

    constexpr T val() const {
      assert(this->is_finite());
      return this->m_value;
    }

    friend constexpr bool operator==(const ::tools::safe_int<T>& x, const ::tools::safe_int<T>& y) {
      constexpr auto table = ::std::array<::std::array<::std::optional<bool>, 3>, 3>({{
        {BQ(), BF(), BF()},
        {BF(), BT(), BF()},
        {BF(), BF(), BF()}
      }});
      if (const auto r = table[f1(x)][f1(y)]; r) return *r;

      return x.m_value == y.m_value;
    }
    friend constexpr bool operator!=(const ::tools::safe_int<T>& x, const ::tools::safe_int<T>& y) {
      return !(x == y);
    }

    constexpr ::tools::safe_int<T> operator+() const {
      return *this;
    }
    constexpr ::tools::safe_int<T> operator-() const {
      constexpr auto table = ::std::array<::std::optional<::tools::safe_int<T>>, 3>({
        {Q(), U(), U()}
      });
      if (const auto r = table[f1(*this)]; r) return *r;

      if (this->m_value > 0) return *U();
      return ::tools::safe_int<T>(0);
    }

    friend constexpr ::tools::safe_int<T> operator+(const ::tools::safe_int<T>& x, const ::tools::safe_int<T>& y) {
      constexpr auto table = ::std::array<::std::array<::std::optional<::tools::safe_int<T>>, 3>, 3>({{
        {Q(), P(), U()},
        {P(), P(), U()},
        {U(), U(), U()}
      }});
      if (const auto r = table[f1(x)][f1(y)]; r) return *r;

      if (y.m_value > 0 && x.m_value > ::std::numeric_limits<T>::max() - y.m_value) return *U();
      return ::tools::safe_int<T>(x.m_value + y.m_value);
    }
    friend constexpr ::tools::safe_int<T> operator+(const ::tools::safe_int<T>& x, const T& y) {
      return x + tools::safe_int<T>(y);
    }
    friend constexpr ::tools::safe_int<T> operator+(const T& x, const ::tools::safe_int<T>& y) {
      return tools::safe_int<T>(x) + y;
    }

    friend constexpr ::tools::safe_int<T> operator-(const ::tools::safe_int<T>& x, const ::tools::safe_int<T>& y) {
      constexpr auto table = ::std::array<::std::array<::std::optional<::tools::safe_int<T>>, 3>, 3>({{
        {Q(), U(), U()},
        {P(), U(), U()},
        {U(), U(), U()}
      }});
      if (const auto r = table[f1(x)][f1(y)]; r) return *r;

      if (x.m_value < y.m_value) return *U();
      return ::tools::safe_int<T>(x.m_value - y.m_value);
    }
    friend constexpr ::tools::safe_int<T> operator-(const ::tools::safe_int<T>& x, const T& y) {
      return x - tools::safe_int<T>(y);
    }
    friend constexpr ::tools::safe_int<T> operator-(const T& x, const ::tools::safe_int<T>& y) {
      return tools::safe_int<T>(x) - y;
    }

    friend constexpr ::tools::safe_int<T> operator*(const ::tools::safe_int<T>& x, const ::tools::safe_int<T>& y) {
      constexpr auto table = ::std::array<::std::array<::std::optional<::tools::safe_int<T>>, 4>, 4>({{
        {Z(), Z(), U(), U()},
        {Z(), Q(), P(), U()},
        {U(), P(), P(), U()},
        {U(), U(), U(), U()}
      }});
      if (const auto r = table[f2(x)][f2(y)]; r) return *r;

      if (x.m_value > ::std::numeric_limits<T>::max() / y.m_value) {
        return *U();
      }
      return ::tools::safe_int<T>(x.m_value * y.m_value);
    }
    friend constexpr ::tools::safe_int<T> operator*(const ::tools::safe_int<T>& x, const T& y) {
      return x * tools::safe_int<T>(y);
    }
    friend constexpr ::tools::safe_int<T> operator*(const T& x, const ::tools::safe_int<T>& y) {
      return tools::safe_int<T>(x) * y;
    }

    friend constexpr ::tools::safe_int<T> operator/(const ::tools::safe_int<T>& x, const ::tools::safe_int<T>& y) {
      constexpr auto table = ::std::array<::std::array<::std::optional<::tools::safe_int<T>>, 4>, 4>({{
        {U(), Z(), Z(), U()},
        {U(), Q(), Z(), U()},
        {U(), P(), U(), U()},
        {U(), U(), U(), U()}
      }});
      if (const auto r = table[f2(x)][f2(y)]; r) return *r;

      return ::tools::safe_int<T>(x.m_value / y.m_value);
    }
    friend constexpr ::tools::safe_int<T> operator/(const ::tools::safe_int<T>& x, const T& y) {
      return x / tools::safe_int<T>(y);
    }
    friend constexpr ::tools::safe_int<T> operator/(const T& x, const ::tools::safe_int<T>& y) {
      return tools::safe_int<T>(x) / y;
    }

    friend constexpr ::tools::safe_int<T> operator%(const ::tools::safe_int<T>& x, const ::tools::safe_int<T>& y) {
      constexpr auto table = ::std::array<::std::array<::std::optional<::tools::safe_int<T>>, 4>, 4>({{
        {U(), Z(), U(), U()},
        {U(), Q(), U(), U()},
        {U(), U(), U(), U()},
        {U(), U(), U(), U()}
      }});
      if (const auto r = table[f2(x)][f2(y)]; r) return *r;

      return ::tools::safe_int<T>(x.m_value % y.m_value);
    }
    friend constexpr ::tools::safe_int<T> operator%(const ::tools::safe_int<T>& x, const T& y) {
      return x % tools::safe_int<T>(y);
    }
    friend constexpr ::tools::safe_int<T> operator%(const T& x, const ::tools::safe_int<T>& y) {
      return tools::safe_int<T>(x) % y;
    }

    constexpr ::tools::safe_int<T>& operator+=(const ::tools::safe_int<T>& other) {
      return *this = *this + other;
    }
    constexpr ::tools::safe_int<T>& operator+=(const T& other) {
      return *this = *this + ::tools::safe_int<T>(other);
    }
    constexpr ::tools::safe_int<T>& operator-=(const ::tools::safe_int<T>& other) {
      return *this = *this - other;
    }
    constexpr ::tools::safe_int<T>& operator-=(const T& other) {
      return *this = *this - ::tools::safe_int<T>(other);
    }
    constexpr ::tools::safe_int<T>& operator*=(const ::tools::safe_int<T>& other) {
      return *this = *this * other;
    }
    constexpr ::tools::safe_int<T>& operator*=(const T& other) {
      return *this = *this * ::tools::safe_int<T>(other);
    }
    constexpr ::tools::safe_int<T>& operator/=(const ::tools::safe_int<T>& other) {
      return *this = *this / other;
    }
    constexpr ::tools::safe_int<T>& operator/=(const T& other) {
      return *this = *this / ::tools::safe_int<T>(other);
    }
    constexpr ::tools::safe_int<T>& operator%=(const ::tools::safe_int<T>& other) {
      return *this = *this % other;
    }
    constexpr ::tools::safe_int<T>& operator%=(const T& other) {
      return *this = *this % ::tools::safe_int<T>(other);
    }

    constexpr ::tools::safe_int<T>& operator++() {
      return *this += ::tools::safe_int<T>(T(1));
    }
    constexpr ::tools::safe_int<T> operator++(int) {
      const auto r = *this;
      ++(*this);
      return r;
    }
    constexpr ::tools::safe_int<T>& operator--() {
      return *this -= ::tools::safe_int<T>(T(1));
    }
    constexpr ::tools::safe_int<T> operator--(int) {
      const auto r = *this;
      --(*this);
      return r;
    }

    friend constexpr bool operator<(const ::tools::safe_int<T>& x, const ::tools::safe_int<T>& y) {
      constexpr auto table = ::std::array<::std::array<::std::optional<bool>, 3>, 3>({{
        {BQ(), BT(), BF()},
        {BF(), BF(), BF()},
        {BF(), BF(), BF()}
      }});
      if (const auto r = table[f1(x)][f1(y)]; r) return *r;

      return x.m_value < y.m_value;
    }
    friend constexpr bool operator>(const ::tools::safe_int<T>& x, const ::tools::safe_int<T>& y) {
      constexpr auto table = ::std::array<::std::array<::std::optional<bool>, 3>, 3>({{
        {BQ(), BF(), BF()},
        {BT(), BF(), BF()},
        {BF(), BF(), BF()}
      }});
      if (const auto r = table[f1(x)][f1(y)]; r) return *r;

      return x.m_value > y.m_value;
    }
    friend constexpr bool operator<=(const ::tools::safe_int<T>& x, const ::tools::safe_int<T>& y) {
      return x < y || x == y;
    }
    friend constexpr bool operator>=(const ::tools::safe_int<T>& x, const ::tools::safe_int<T>& y) {
      return x > y || x == y;
    }

    friend ::std::istream& operator>>(::std::istream& is, ::tools::safe_int<T>& self) {
      self.m_type = ::tools::safe_int<T>::type::finite;
      return is >> self.m_value;
    }
    friend ::std::ostream& operator<<(::std::ostream& os, const ::tools::safe_int<T>& self) {
      switch (self.m_type) {
      case ::tools::safe_int<T>::type::finite:
        return os << self.m_value;
      case ::tools::safe_int<T>::type::pos_inf:
        return os << "inf";
      default: // nan
        return os << "nan";
      }
    }
  };
}


#line 1 "tools/ceil.hpp"



#line 1 "tools/is_integral.hpp"



#line 5 "tools/is_integral.hpp"

namespace tools {
  template <typename T>
  struct is_integral : ::std::is_integral<T> {};

  template <typename T>
  inline constexpr bool is_integral_v = ::tools::is_integral<T>::value;
}


#line 1 "tools/is_unsigned.hpp"



#line 5 "tools/is_unsigned.hpp"

namespace tools {
  template <typename T>
  struct is_unsigned : ::std::is_unsigned<T> {};

  template <typename T>
  inline constexpr bool is_unsigned_v = ::tools::is_unsigned<T>::value;
}


#line 8 "tools/ceil.hpp"

namespace tools {
  template <typename M, typename N> requires (
    ::tools::is_integral_v<M> && !::std::is_same_v<::std::remove_cv_t<M>, bool> &&
    ::tools::is_integral_v<N> && !::std::is_same_v<::std::remove_cv_t<N>, bool>)
  constexpr ::std::common_type_t<M, N> ceil(const M x, const N y) noexcept {
    assert(y != 0);
    if (y >= 0) {
      if (x > 0) {
        return (x - 1) / y + 1;
      } else {
        if constexpr (::tools::is_unsigned_v<::std::common_type_t<M, N>>) {
          return 0;
        } else {
          return x / y;
        }
      }
    } else {
      if (x >= 0) {
        if constexpr (::tools::is_unsigned_v<::std::common_type_t<M, N>>) {
          return 0;
        } else {
          return x / y;
        }
      } else {
        return (x + 1) / y + 1;
      }
    }
  }
}


#line 1 "tools/pow2.hpp"



#line 6 "tools/pow2.hpp"

namespace tools {

  template <typename T, typename ::std::enable_if<::std::is_unsigned<T>::value, ::std::nullptr_t>::type = nullptr>
  constexpr T pow2(const T x) {
    return static_cast<T>(1) << x;
  }

  template <typename T, typename ::std::enable_if<::std::is_signed<T>::value, ::std::nullptr_t>::type = nullptr>
  constexpr T pow2(const T x) {
    return static_cast<T>(static_cast<typename ::std::make_unsigned<T>::type>(1) << static_cast<typename ::std::make_unsigned<T>::type>(x));
  }
}


#line 20 "tools/zero_one_knapsack.hpp"

namespace tools {
  template <typename T>
  class zero_one_knapsack {
  private:
    T m_W;
    ::std::vector<::std::pair<T, T>> m_items;

  public:
    zero_one_knapsack() = default;
    zero_one_knapsack(const ::tools::zero_one_knapsack<T>&) = default;
    zero_one_knapsack(::tools::zero_one_knapsack<T>&&) = default;
    ~zero_one_knapsack() = default;
    ::tools::zero_one_knapsack<T>& operator=(const ::tools::zero_one_knapsack<T>&) = default;
    ::tools::zero_one_knapsack<T>& operator=(::tools::zero_one_knapsack<T>&&) = default;

    explicit zero_one_knapsack(const T W) : m_W(W) {
      assert(W >= 0);
    }

    ::std::size_t size() const {
      return this->m_items.size();
    }

    T capacity() const {
      return this->m_W;
    }

    ::std::size_t add_item(const T v, const T w) {
      assert(v >= 0);
      assert(w >= 0);
      this->m_items.emplace_back(v, w);
      return this->m_items.size() - 1;
    }

    ::std::pair<T, T> get_item(const ::std::size_t k) const {
      assert(k < this->m_items.size());
      return this->m_items[k];
    }

    const ::std::vector<::std::pair<T, T>>& items() const {
      return this->m_items;
    }

  private:
    ::std::pair<T, ::std::vector<::std::size_t>> solve_by_dp_maximizing_value() const {
      auto dp = ::std::vector(this->size() + 1, ::std::vector(this->m_W + 1, ::std::numeric_limits<T>::min()));
      dp[0][0] = 0;
      for (::std::size_t i = 1; i <= this->size(); ++i) {
        const auto [v, w] = this->m_items[i - 1];
        for (T j = 0; j <= this->m_W; ++j) {
          dp[i][j] = dp[i - 1][j];
          if (j >= w && dp[i - 1][j - w] >= 0) {
            ::tools::chmax(dp[i][j], dp[i - 1][j - w] + v);
          }
        }
      }

      ::std::pair<T, ::std::vector<::std::size_t>> res;
      auto& [answer, selected] = res;
      T left = ::std::distance(dp[this->size()].begin(), ::std::max_element(dp[this->size()].begin(), dp[this->size()].end()));
      answer = dp[this->size()][left];
      for (::std::size_t i = this->size(); i --> 0;) {
        const auto [v, w] = this->m_items[i];
        if (dp[i + 1][left] != dp[i][left]) {
          assert(left >= w);
          assert(dp[i + 1][left] == dp[i][left - w] + v);
          selected.push_back(i);
          left -= w;
        }
      }
      assert(left == 0);

      ::std::reverse(selected.begin(), selected.end());
      return res;
    }

    ::std::pair<T, ::std::vector<::std::size_t>> solve_by_dp_minimizing_weight() const {
      const auto max_V = ::std::accumulate(this->m_items.begin(), this->m_items.end(), static_cast<T>(0), [](const auto sum, const auto& item) { return sum + item.first; });
      auto dp = ::std::vector(this->size() + 1, ::std::vector(max_V + 1, ::std::numeric_limits<T>::max()));
      dp[0][0] = 0;
      for (::std::size_t i = 1; i <= this->size(); ++i) {
        const auto [v, w] = this->m_items[i - 1];
        for (T j = 0; j <= max_V; ++j) {
          dp[i][j] = dp[i - 1][j];
          if (j >= v && dp[i - 1][j - v] < ::std::numeric_limits<T>::max() && dp[i - 1][j - v] + w <= this->m_W) {
            ::tools::chmin(dp[i][j], dp[i - 1][j - v] + w);
          }
        }
      }

      ::std::pair<T, ::std::vector<::std::size_t>> res;
      auto& [answer, selected] = res;
      answer = ::std::distance(dp[this->size()].begin(), ::std::prev(::std::find_if(dp[this->size()].rbegin(), dp[this->size()].rend(), [](const auto w) { return w < ::std::numeric_limits<T>::max(); }).base()));
      T left = answer;
      for (::std::size_t i = this->size(); i --> 0;) {
        const auto [v, w] = this->m_items[i];
        if (dp[i + 1][left] != dp[i][left]) {
          assert(left >= v);
          assert(dp[i + 1][left] == dp[i][left - v] + w);
          selected.push_back(i);
          left -= v;
        }
      }
      assert(left == 0);

      ::std::reverse(selected.begin(), selected.end());
      return res;
    }

    ::std::pair<T, ::std::vector<::std::size_t>> solve_by_meet_in_the_middle() const {
      const auto f = [&](const ::std::size_t L, const ::std::size_t R) {
        ::std::vector<::std::tuple<::std::size_t, T, T>> res;
        res.emplace_back(0, 0, 0);
        for (::std::size_t i = L; i < R; ++i) {
          ::std::size_t n = res.size();
          for (::std::size_t j = 0; j < n && ::std::get<2>(res[j]) + this->m_items[i].second <= this->m_W; ++j) {
            res.emplace_back(::std::get<0>(res[j]) | (static_cast<::std::size_t>(1) << (i - L)), ::std::get<1>(res[j]) + this->m_items[i].first, ::std::get<2>(res[j]) + this->m_items[i].second);
          }
          ::std::inplace_merge(res.begin(), res.begin() + n, res.end(), ::tools::less_by_get<2>());
        }

        for (::std::size_t l = 0, r = 0; l < res.size(); l = r) {
          for (; r < res.size() && ::std::get<2>(res[l]) == ::std::get<2>(res[r]); ++r);
          ::std::iter_swap(res.begin() + l, ::std::max_element(res.begin() + l, res.begin() + r, ::tools::less_by_get<1>()));
        }

        ::std::size_t vl = 0;
        for (::std::size_t vr = 0, al = 0, ar = 0; al < res.size(); vl = vr, al = ar) {
          for (; ar < res.size() && ::std::get<1>(res[al]) >= ::std::get<1>(res[ar]); ++vr, ++ar);
          if (vl < al) ::std::move(res.begin() + al, res.begin() + ar, res.begin() + vl);
          vr = vl + 1;
        }
        res.erase(res.begin() + vl, res.end());

        return res;
      };

      const auto first_half = f(0, this->size() / 2);
      const auto second_half = f(this->size() / 2, this->size());

      ::std::pair<T, ::std::vector<::std::size_t>> res;
      auto& [answer, selected] = res;
      answer = ::std::numeric_limits<T>::min();
      ::std::pair<::std::size_t, ::std::size_t> selected_as_bitset;
      ::std::size_t r = second_half.size();
      for (const auto& [state, v, w] : first_half) {
        for (; w + ::std::get<2>(second_half[r - 1]) > this->m_W; --r);
        if (::tools::chmax(answer, v + ::std::get<1>(second_half[r - 1]))) {
          selected_as_bitset = ::std::make_pair(state, ::std::get<0>(second_half[r - 1]));
        }
      }

      for (::std::size_t i = 0; i < this->size() / 2; ++i) {
        if (selected_as_bitset.first & (static_cast<::std::size_t>(1) << i)) {
          selected.push_back(i);
        }
      }
      for (::std::size_t i = this->size() / 2; i < this->size(); ++i) {
        if (selected_as_bitset.second & (static_cast<::std::size_t>(1) << (i - this->size() / 2))) {
          selected.push_back(i);
        }
      }

      return res;
    }

  public:
    ::std::pair<T, ::std::vector<::std::size_t>> query() const {
      using S = ::tools::safe_int<long long>;
      ::std::array<S, 3> complexities = {
        S(this->size()) * S(this->m_W),
        S(this->size()) * ::std::accumulate(this->m_items.begin(), this->m_items.end(), S(0), [](const auto sum, const auto& item) { return sum + S(item.first); }),
        ::tools::ceil(this->size(), 2) < ::std::numeric_limits<long long>::digits ? S(::tools::pow2<long long>(::tools::ceil(this->size(), 2))) : S::nan(),
      };
      for (auto& complexity : complexities) {
        if (complexity.is_nan()) complexity = S::infinity();
      }
      const auto min_complexity = *::std::min_element(complexities.begin(), complexities.end());
      if (complexities[0] == min_complexity) {
        return this->solve_by_dp_maximizing_value();
      } else if (complexities[1] == min_complexity) {
        return this->solve_by_dp_minimizing_weight();
      } else {
        return this->solve_by_meet_in_the_middle();
      }
    }
  };
}


#line 1 "tools/assert_that.hpp"



#line 5 "tools/assert_that.hpp"
#include <cstdlib>

#define assert_that_impl(cond, file, line, func) do {\
  if (!cond) {\
    ::std::cerr << file << ':' << line << ": " << func << ": Assertion `" << #cond << "' failed." << '\n';\
    ::std::exit(EXIT_FAILURE);\
  }\
} while (false)
#define assert_that(...) assert_that_impl((__VA_ARGS__), __FILE__, __LINE__, __func__)


#line 6 "tests/zero_one_knapsack/solve_by_dp_maximizing_value.test.cpp"

using ll = long long;

int main() {
  std::cin.tie(nullptr);
  std::ios_base::sync_with_stdio(false);

  ll N, W;
  std::cin >> N >> W;
  tools::zero_one_knapsack<ll> solver(W);
  for (ll i = 0; i < N; ++i) {
    ll v, w;
    std::cin >> v >> w;
    solver.add_item(v, w);
  }

  const auto [answer, selected] = solver.query();
  ll v = 0;
  ll w = 0;
  for (const auto i : selected) {
    v += solver.get_item(i).first;
    w += solver.get_item(i).second;
  }
  assert_that(v == answer);
  assert_that(w <= W);
  std::cout << answer << '\n';

  return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	00_sample_00.in	AC	4 ms	4 MB
g++	00_sample_01.in	AC	4 ms	4 MB
g++	01_small_00.in	AC	4 ms	3 MB
g++	01_small_01.in	AC	4 ms	4 MB
g++	01_small_02.in	AC	4 ms	4 MB
g++	01_small_03.in	AC	4 ms	4 MB
g++	02_rand_00.in	AC	4 ms	4 MB
g++	02_rand_01.in	AC	4 ms	4 MB
g++	02_rand_02.in	AC	4 ms	4 MB
g++	02_rand_03.in	AC	4 ms	4 MB
g++	02_rand_04.in	AC	4 ms	4 MB
g++	02_rand_05.in	AC	4 ms	4 MB
g++	02_rand_06.in	AC	4 ms	4 MB
g++	02_rand_07.in	AC	4 ms	4 MB
g++	02_rand_08.in	AC	4 ms	4 MB
g++	02_rand_09.in	AC	4 ms	4 MB
g++	03_corner_00.in	AC	4 ms	4 MB
g++	03_corner_01.in	AC	4 ms	4 MB
g++	03_corner_02.in	AC	4 ms	4 MB
g++	03_corner_03.in	AC	4 ms	4 MB
g++	03_medium_00.in	AC	4 ms	4 MB
g++	03_medium_01.in	AC	5 ms	5 MB
g++	03_medium_02.in	AC	7 ms	7 MB
g++	03_medium_03.in	AC	7 ms	7 MB
g++	04_large_00.in	AC	4 ms	4 MB
g++	04_large_01.in	AC	4 ms	4 MB
g++	04_large_02.in	AC	4 ms	4 MB
g++	04_large_03.in	AC	4 ms	4 MB
g++	04_large_04.in	AC	5 ms	6 MB
g++	04_large_05.in	AC	7 ms	7 MB
g++	04_large_06.in	AC	8 ms	9 MB
g++	04_large_07.in	AC	10 ms	11 MB
g++	05_maximum_00.in	AC	9 ms	11 MB
g++	05_maximum_01.in	AC	9 ms	11 MB
g++	05_maximum_02.in	AC	9 ms	11 MB
g++	05_maximum_03.in	AC	10 ms	11 MB

Back to top page