test/aoj/DPL_1_G/main.test.cpp
Depends on
Code
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_G"
#include <iostream>
#include <vector>
#include "Mylib/IO/input_tuple_vector.cpp"
#include "Mylib/Typical/knapsack_limited.cpp"
namespace hl = haar_lib;
int main() {
int N, W;
std::cin >> N >> W;
auto [v, w, m] = hl::input_tuple_vector<int, int, int>(N);
auto ans = hl::knapsack_limited(N, W, w, v, m);
std::cout << ans << std::endl;
return 0;
}
#line 1 "test/aoj/DPL_1_G/main.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_G"
#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_limited.cpp"
#include <algorithm>
#line 4 "Mylib/Typical/knapsack_limited.cpp"
namespace haar_lib {
template <typename Weight, typename Value>
Value knapsack_limited(int N, Weight cap, const std::vector<Weight> &w, const std::vector<Value> &v, const std::vector<int> &m) {
std::vector<Value> dp(cap + 1);
for (int i = 0; i < N; ++i) {
for (int64_t a = 1, x = m[i], k; k = std::min(x, a), x > 0; x -= k, a *= 2) {
for (int j = cap; j >= 0; --j) {
if (j - k * w[i] >= 0) {
dp[j] = std::max(dp[j], dp[j - k * w[i]] + (Weight) k * v[i]);
}
}
}
}
return dp[cap];
}
} // namespace haar_lib
#line 7 "test/aoj/DPL_1_G/main.test.cpp"
namespace hl = haar_lib;
int main() {
int N, W;
std::cin >> N >> W;
auto [v, w, m] = hl::input_tuple_vector<int, int, int>(N);
auto ans = hl::knapsack_limited(N, W, w, v, m);
std::cout << ans << std::endl;
return 0;
}
Back to top page
Input tuple vector
(Mylib/IO/input_tuple_vector.cpp)