Submission #1126138

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126138		subham_krr	Knapsack (NOI18_knapsack)	C++20	73 / 100	285 ms	327680 KiB

knapsack

#include <bits/stdc++.h>
#define int long long
using namespace std;

signed main() {
    int s, n;
    cin >> s >> n;

    vector<vector<int> > v(n, vector<int>(3)); // Stores {value, weight, max_quantity}
    for (int i = 0; i < n; i++) {
        int value, weight, max_quantity;
        cin >> value >> weight >> max_quantity;
        v[i][0] = value;  // Store value
        v[i][1] = weight; // Store weight
        v[i][2] = max_quantity; // Store max_quantity
    }

    vector<vector<int> > dp(n + 1, vector<int>(s + 1, 0)); // DP table

    for (int i = n - 1; i >= 0; i--) { // Iterate over items
        for (int j = 0; j <= s; j++) { // Iterate over possible capacities
            dp[i][j] = dp[i + 1][j]; // Case: Don't take the item
            int d=s/v[i][1]+1;
            for (int k = 1; k <= min(v[i][2],d); k++) { // Consider all quantities up to max_quantity
                int weight = k * v[i][1]; 
                if (j >= weight) {
                    dp[i][j] = max(dp[i][j], k * v[i][0] + dp[i + 1][j - weight]);
                }
            }
        }
    }

    cout << dp[0][s] << endl; // Maximum value achievable with total capacity `s`
}

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