verify/aoj_dpl/aoj_dpl_1_g.test.cpp

• View this file on GitHub
• Last update: 2023-02-06 19:40:21+09:00
• Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_G

Depends on

• Knapsack Limitations (個数制限付きナップサック問題) (dp/knapsack_limitations.hpp)

Code

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

#include <bits/stdc++.h>

#include "dp/knapsack_limitations.hpp"

int main() {
    int N, W;
    std::cin >> N >> W;
    std::vector<int> v(N), w(N), m(N);
    for (int i = 0; i < N; i++) std::cin >> v[i] >> w[i] >> m[i];
    auto ret1 = knapsack_limitations(w, v, m, W, -1);
    auto ans1 = *std::max_element(ret1.begin(), ret1.end());
    for (int i = 0; i < N; i++) v[i] = -v[i];
    auto ret2 = knapsack_limitations(w, v, m, W, 1, std::less<int>());
    auto ans2 = *std::min_element(ret2.begin(), ret2.end());
    assert(ans1 == -ans2);
    std::cout << ans1 << '\n';
    return 0;
}

#line 1 "verify/aoj_dpl/aoj_dpl_1_g.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_G"

#include <bits/stdc++.h>

#line 2 "dp/knapsack_limitations.hpp"

template <class T, class F = std::greater<T>>
std::vector<T> knapsack_limitations(const std::vector<int> &w, const std::vector<T> &v, const std::vector<int> &m,  //
                                    const int W, const T &e, const F &comp = F(), const int s = 0) {
    const int n = (int)w.size();
    std::vector<T> dp(W + 1, e), deqv(W + 1);
    std::vector<int> deq(W + 1);
    dp[s] = T(0);
    for (int i = 0; i < n; i++) {
        if (w[i] > 0) {
            for (int a = 0; a < w[i]; a++) {
                int s = 0, t = 0;
                for (int j = 0; a + j * w[i] <= W; j++) {
                    if (dp[a + j * w[i]] != e) {
                        T val = dp[a + j * w[i]] - j * v[i];
                        while (s < t and comp(val, deqv[t - 1])) t--;
                        deq[t] = j;
                        deqv[t++] = val;
                    }
                    if (s < t) {
                        dp[a + j * w[i]] = deqv[s] + j * v[i];
                        if (deq[s] == j - m[i]) s++;
                    }
                }
            }
        } else if (w[i] < 0) {
            for (int a = 0; a < -w[i]; a++) {
                int s = 0, t = 0;
                for (int j = 0; W - a + j * w[i] >= 0; j++) {
                    if (dp[W - a + j * w[i]] != e) {
                        T val = dp[W - a + j * w[i]] - j * v[i];
                        while (s < t and comp(val, deqv[t - 1])) t--;
                        deq[t] = j;
                        deqv[t++] = val;
                    }
                    if (s < t) {
                        dp[W - a + j * w[i]] = deqv[s] + j * v[i];
                        if (deq[s] == j - m[i]) s++;
                    }
                }
            }
        } else {
            // w[i] = 0
            continue;
        }
    }
    return dp;
}
#line 6 "verify/aoj_dpl/aoj_dpl_1_g.test.cpp"

int main() {
    int N, W;
    std::cin >> N >> W;
    std::vector<int> v(N), w(N), m(N);
    for (int i = 0; i < N; i++) std::cin >> v[i] >> w[i] >> m[i];
    auto ret1 = knapsack_limitations(w, v, m, W, -1);
    auto ans1 = *std::max_element(ret1.begin(), ret1.end());
    for (int i = 0; i < N; i++) v[i] = -v[i];
    auto ret2 = knapsack_limitations(w, v, m, W, 1, std::less<int>());
    auto ans2 = *std::min_element(ret2.begin(), ret2.end());
    assert(ans1 == -ans2);
    std::cout << ans1 << '\n';
    return 0;
}

Back to top page