Submission #792225

#	Time	Username	Problem	Language	Result	Execution time	Memory
792225		gtm7	Knapsack (NOI18_knapsack)	C++17	100 / 100	119 ms	8012 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int s, n;
    cin >> s >> n;
    vector<vector<int>> a(n, vector<int>(3)); // w,v,k
    for (int i = 0; i < n; i++)
    {
        cin >> a[i][1] >> a[i][0] >> a[i][2];
        a[i][1] = -a[i][1];
    }
    sort(a.begin(), a.end());
    vector<int> w;
    vector<int> v;
    int rm = 0, ct = 0;
    for (int i = 0; i < n; i++)
    {
        if ((i == 0) || (a[i][0] != a[i - 1][0]))
        {
            rm = s / a[i][0];
            ct = min(a[i][2], rm);
            for (int j = 0; j < ct; j++)
            {
                w.push_back(a[i][0]);
                v.push_back(-a[i][1]);
            }
            rm -= ct;
        }
        else
        {
            ct = min(a[i][2], rm);
            for (int j = 0; j < ct; j++)
            {
                w.push_back(a[i][0]);
                v.push_back(-a[i][1]);
            }
            rm -= ct;
        }
    }
    int nn = w.size();
    vector<int> dp(s + 1, 0);
    for (int i = 0; i < nn; i++)
    {
        for (int j = s; j >= w[i]; j--)
        {
            dp[j] = max(dp[j], v[i] + dp[j - w[i]]);
        }
    }
    cout << dp[s] << endl;
    return 0;
}

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