Submission #856561

#	Time	Username	Problem	Language	Result	Execution time	Memory
856561		owenlol	Knapsack (NOI18_knapsack)	C++17	0 / 100	1 ms	1116 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int S, N;
    cin >> S >> N;
    vector<int> ws;
    vector<int> vs;
    vector<int> ks;
    for (int i=0; i<N; i++) {
        int v, w, k;
        cin >> v >> w >> k;
        vs.push_back(v);
        ws.push_back(w);
        ks.push_back(k);
    }
    
    vector<vector<int>> dp(S+1, vector<int>(N+1));
    for (int i=0; i<S; i++) {
        dp[i][0] = 0;
    }
    for (int i=0; i<N; i++) {
        dp[0][i] = 0;
    }
    for (int s=1; s<S+1; s++) {
        for (int i=1; i<N+1; i++) {
            for (int r=1; r<=ks[i]; r++) {
                if (s >= r*ws[i]) {
                    dp[s][i] = max(dp[s][i], dp[s-r*ws[i]][i-1] + r*vs[i]);
                }
            }
            dp[s][i] = max(dp[s][i], dp[s][i-1]);

        }
    }

    cout << dp[S][N];
    return 0;
}

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