test/aoj/DPL_1_H/main.test.cpp

• View this file on GitHub
• Last update: 2021-04-23 23:44:44+09:00
• Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_H
• Link: View error logs on GitHub Actions

Depends on

• Input tuple vector (Mylib/IO/input_tuple_vector.cpp)
• 0-1 Knapsack problem (Small quantity) (Mylib/Typical/knapsack_small_quantity.cpp)

Code

#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_H"

#include <iostream>
#include <vector>
#include "Mylib/IO/input_tuple_vector.cpp"
#include "Mylib/Typical/knapsack_small_quantity.cpp"

namespace hl = haar_lib;

int main() {
  int N;
  std::cin >> N;
  int64_t W;
  std::cin >> W;

  auto [v, w] = hl::input_tuple_vector<int64_t, int64_t>(N);

  auto ans = hl::knapsack_small_quantity(N, W, w, v);

  std::cout << ans << std::endl;

  return 0;
}

#line 1 "test/aoj/DPL_1_H/main.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_H"

#include <iostream>
#include <vector>
#line 2 "Mylib/IO/input_tuple_vector.cpp"
#include <initializer_list>
#line 4 "Mylib/IO/input_tuple_vector.cpp"
#include <tuple>
#include <utility>
#line 7 "Mylib/IO/input_tuple_vector.cpp"

namespace haar_lib {
  template <typename T, size_t... I>
  void input_tuple_vector_init(T &val, int N, std::index_sequence<I...>) {
    (void) std::initializer_list<int>{(void(std::get<I>(val).resize(N)), 0)...};
  }

  template <typename T, size_t... I>
  void input_tuple_vector_helper(T &val, int i, std::index_sequence<I...>) {
    (void) std::initializer_list<int>{(void(std::cin >> std::get<I>(val)[i]), 0)...};
  }

  template <typename... Args>
  auto input_tuple_vector(int N) {
    std::tuple<std::vector<Args>...> ret;

    input_tuple_vector_init(ret, N, std::make_index_sequence<sizeof...(Args)>());
    for (int i = 0; i < N; ++i) {
      input_tuple_vector_helper(ret, i, std::make_index_sequence<sizeof...(Args)>());
    }

    return ret;
  }
}  // namespace haar_lib
#line 2 "Mylib/Typical/knapsack_small_quantity.cpp"
#include <algorithm>
#include <iterator>
#include <map>
#line 6 "Mylib/Typical/knapsack_small_quantity.cpp"

namespace haar_lib {
  template <typename Weight, typename Value>
  Value knapsack_small_quantity(int N, Weight cap, const std::vector<Weight> &w, const std::vector<Value> &v) {
    const int p = N / 2;
    const int q = N - p;

    std::vector<std::pair<Weight, Value>> a, b;
    a.reserve(1 << p);
    b.reserve(1 << q);

    a.emplace_back(0, 0);
    b.emplace_back(0, 0);

    for (int i = 0; i < p; ++i) {
      const int k      = a.size();
      const auto begin = a.begin();
      const auto end   = a.end();

      for (auto it = begin; it != end; ++it) {
        a.emplace_back(it->first + w[i], it->second + v[i]);
      }

      std::inplace_merge(a.begin(), a.begin() + k, a.end());
    }

    for (int i = p; i < p + q; ++i) {
      const int k      = b.size();
      const auto begin = b.begin();
      const auto end   = b.end();

      for (auto it = begin; it != end; ++it) {
        b.emplace_back(it->first + w[i], it->second + v[i]);
      }

      std::inplace_merge(b.begin(), b.begin() + k, b.end());
    }

    for (size_t i = 1; i < a.size(); ++i) {
      a[i].second = std::max(a[i].second, a[i - 1].second);
    }

    for (size_t i = 1; i < b.size(); ++i) {
      b[i].second = std::max(b[i].second, b[i - 1].second);
    }

    Value ret = 0;

    for (int i = 0, j = (int) b.size() - 1; i < (int) a.size(); ++i) {
      while (j >= 0 and a[i].first + b[j].first > cap) --j;
      if (j < 0) break;
      ret = std::max(ret, a[i].second + b[j].second);
    }

    return ret;
  }
}  // namespace haar_lib
#line 7 "test/aoj/DPL_1_H/main.test.cpp"

namespace hl = haar_lib;

int main() {
  int N;
  std::cin >> N;
  int64_t W;
  std::cin >> W;

  auto [v, w] = hl::input_tuple_vector<int64_t, int64_t>(N);

  auto ans = hl::knapsack_small_quantity(N, W, w, v);

  std::cout << ans << std::endl;

  return 0;
}

Back to top page