Submission #974903

#	Time	Username	Problem	Language	Result	Execution time	Memory
974903		vjudge1	Knapsack (NOI18_knapsack)	C++17	73 / 100	760 ms	262144 KiB

knapsack

#include <bits/stdc++.h>

using namespace std;

int knapsack(int S, const vector<int> &V, const vector<int> &W, const vector<int> &K)
{
    int N = V.size();
    vector<vector<int>> dp(N + 1, vector<int>(S + 1, 0));

    for (int i = 1; i <= N; i++)
    {
        for (int j = 0; j <= S; j++)
        {
            for (int k = 0; k <= min(j / W[i - 1], K[i - 1]); ++k)
            {
                dp[i][j] = max(dp[i][j], dp[i - 1][j - k * W[i - 1]] + k * V[i - 1]);
            }
        }
    }

    return dp[N][S];
}
void solve()
{
    int s, n;
    cin >> s >> n;

    vector<int> v(n), w(n), k(n);
    for (int i = 0; i < n; i++)
    {
        cin >> v[i] >> w[i] >> k[i];
    }

    cout << knapsack(s, v, w, k);
}

int main()
{

    int t = 1;
    while (t--)
    {
        solve();
    }
    return 0;
}

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