Submission #1354682

#	Time	Username	Problem	Language	Result	Execution time	Memory
1354682		meme_boi2	Knapsack (NOI18_knapsack)	C++20	73 / 100	1095 ms	5088 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
class Solution{
    public:
        long long CalculateKnapsack(int S, vector<array<long long,3>> items){
            int n = items.size();
            sort(items.begin(),items.end());
            // v, w, k
            vector<long long> dp(S+1,0);
            long long ans = 0;
            for(int i = 0; i < n; i++){
                for(int j = S; j >= 0; j--){
                    for(int t = 1; t <= items[i][2] && j - t * items[i][1] >= 0; t++){
                        dp[j] = max(dp[j], dp[j - t * items[i][1]] + t * items[i][0]);
                        ans = max(ans,dp[j]);
                    }
                }
            }
            return ans;
        }
};
int32_t main(){
    cin.tie(nullptr)->sync_with_stdio(0);
    int q = 1;
    //cin >> q;    
    Solution sol;
    while(q--){
        int S; int N;
        cin >> S >> N;
        vector<array<long long,3>> items(N);
        for(auto &[V,W,K] : items){
            cin >> V >> W >> K;
        }
        cout << sol.CalculateKnapsack(S,items) << '\n';
    }
}

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