Submission #1352747

#	Time	Username	Problem	Language	Result	Execution time	Memory
1352747		kanapojpm	Knapsack (NOI18_knapsack)	C++20	100 / 100	724 ms	444 KiB

knapsack

#include<iostream>
#include<vector>
#define int long long
using namespace std;
signed main(){
    int n,m;
    cin >> n >> m;
    vector<int> dp(n+1,0);
    for(int i=0;i<m;i++){
        int v,w,k;
        cin >> v >> w >> k;
        for(int x=1;k>0;x*=2){
            int num = min(x,k);
            int wi = w*num;
            int vi = v*num;
            for(int j=n;j>=wi;j--){
                dp[j] = max(dp[j],dp[j-wi]+vi);
            }
            k-=num;
        }
    }
    int ans=0;
    for(int i=0;i<n+1;i++) 
        ans= max(ans,dp[i]);
    cout << ans;
}

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