Submission #976659

#	Time	Username	Problem	Language	Result	Execution time	Memory
976659		vjudge1	Knapsack (NOI18_knapsack)	C++17	73 / 100	1064 ms	3668 KiB

knapsack

#include <iostream>
using namespace std;

struct Kue {
    long long value, weight, stock;
};

int main() {
    int s, n;
    cin >> s >> n;
    Kue kue[n];
    long long total_stock = 0;
    for (int i = 0; i < n; i++) {
        cin >> kue[i].value >> kue[i].weight >> kue[i].stock;
        total_stock += kue[i].stock;
    }
    
    long long dp[s + 1] = {0};
    int k = 0;
    for (int i = 0; i < n; i++) {
        for (int w = s; w >= 0; w--) {
            auto [val, weight, stock] = kue[i];
            if (weight > w) break;
            k = min(w / weight, stock);
            for (int j = 1; j <= k; j++) {
                dp[w] = max(dp[w], dp[w - j * weight] + j * val);
            }
        }
    }
    
    cout << dp[s];
}

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