Submission #856564

#	Time	Username	Problem	Language	Result	Execution time	Memory
856564		owenlol	Knapsack (NOI18_knapsack)	C++17	73 / 100	224 ms	262144 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int S, N;
    cin >> S >> N;
    vector<int> ws;
    ws.push_back(0);
    vector<int> vs;
    vs.push_back(0);
    vector<int> ks;
    ks.push_back(0);

    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]));
                } else {
                    break;
                }
            }
            dp[s][i] = max(dp[s][i], dp[s][i-1]);

        }
    }

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

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