제출 #1201377

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1201377		amanthaband	Knapsack (NOI18_knapsack)	C++20	37 / 100	3 ms	6468 KiB

knapsack

#include <iostream>
#include <vector>
using namespace std;

using ll = long long;

ll solve(vector<int> v, vector<int> w, vector<int> k, int S, int n) {
    vector<int> vv, ww;
    
    for (int i = 1; i <= n; ++i) {
        int value = v[i];
        int weight = w[i];
        int count = k[i];

        for (int b = 1; count > 0; b *= 2) {
            int take = min(b, count);
            vv.push_back(value * take);
            ww.push_back(weight * take);
            count -= take;
        }
    }

    int m = vv.size();
    vector<vector<ll>> dp(m + 1, vector<ll>(S + 1, 0));

    for (int i = 1; i <= m; ++i) {
        for (int j = 0; j <= S; ++j) {
            if (j >= ww[i - 1])
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - ww[i - 1]] + vv[i - 1]);
            else
                dp[i][j] = dp[i - 1][j];
        }
    }

    return dp[m][S];
}

int main() {
    int S, N;
    cin >> S >> N;

    vector<int> v(N + 1), w(N + 1), k(N + 1);
    for (int i = 1; i <= N; ++i) {
        cin >> v[i] >> w[i] >> k[i];
    }

    cout << solve(v, w, k, S, N) << endl;
}

• Subtask 1: 0 / 12
• Subtask 2: 17 / 17
• Subtask 3: 20 / 20
• Subtask 4: 0 / 24
• Subtask 5: 0 / 27