Submission #1346494

#	Time	Username	Problem	Language	Result	Execution time	Memory
1346494		SW_143	Knapsack (NOI18_knapsack)	C++20	100 / 100	687 ms	8732 KiB

knapsack

#include <bits/stdc++.h>
#define ll long long int

using namespace std;

int main()
{   
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int S, N; cin>>S>>N; 
    
    vector<pair<int,int>> items;
    
    for(int i = 1; i<=N; ++i)
    {
        int v, w, k; cin>>v>>w>>k;
        int cap = min(k, S/w); 
        int rem = cap; 
        
        for(int b = 1; rem>0; b*=2)
        {
            int idk = min(b, rem); 
            items.push_back({w*idk, v*idk}); 
            rem -= idk;
        }
    }
    
    vector<ll> dp(S+1, 0);
    
    for(auto [w,v]: items)
    {
        for(int j = S; j>=w; --j)
        {
            dp[j] = max(dp[j], dp[j-w] + v);
        }
    }
    
    cout<<dp[S]<<'\n';
    
    return 0;
}

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