Submission #1246013

#	Time	Username	Problem	Language	Result	Execution time	Memory
1246013		blackmonkey48	Knapsack (NOI18_knapsack)	C++20	12 / 100	1 ms	1096 KiB

knapsack

//=======================================================================================================================================================================================================================================================================================================================
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define fi first
#define se second
#define pii pair<int,int>


int main() {
    ios_base::sync_with_stdio(false);cin.tie(nullptr);
    int s,n; cin >> s >> n;
    int v[n],w[n],k[n];
    for(int i=1;i<=n;i++){
        cin >> v[i] >> w[i] >> k[i];
    }
    vector<vector<int>> dp(n+5,vector<int>(s+5,0));
    for(int i=0;i<=n;i++){
        for(int j=0;j<=s;j++){
            if(i==0 || j==0) {dp[i][j]=0; continue;}
            for(int t=1;t<=k[i] && t*w[i]<=j;t++){
                dp[i][j]=dp[i-1][j];
                if(w[i] <= j) {
                    dp[i][j]=max(dp[i][j], dp[i-1][j-t*w[i]] + t*v[i]);
                }
            }
        }
    }
    // for(int i=0;i<=n;i++){
    //     for(int j=0;j<=s;j++){
    //         cout << dp[i][j] << " ";
    //     } cout << endl;
    // }
    cout << dp[n][s] << endl;
}

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