Submission #785615

#	Time	Username	Problem	Language	Result	Execution time	Memory
785615		0x34c	Knapsack (NOI18_knapsack)	C++17	100 / 100	104 ms	3668 KiB

knapsack

#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>

using namespace std;

int main()
{
    int S, N;
    cin >> S >> N;

    vector<vector<pii>> wei(S + 1);
    for (int i = 0; i < N; i++)
    {
        int v, w, k;
        cin >> v >> w >> k;

        wei[w].push_back({v, k});
    }

    for (int i = 1; i <= S; i++)
        sort(wei[i].begin(), wei[i].end(), greater<pii>());

    vector<ll> dp(S + 1, 0);
    ll ans = 0;
    for (int i = 1; i <= S; i++)
    {
        int idx = 0;
        for (int j = 0; j < S / i && idx < wei[i].size(); j++)
        {
            for (int k = S; k >= i; k--)
            {
                dp[k] = max(dp[k], dp[k - i] + wei[i][idx].first);
                ans = max(ans, dp[k]);
            }
            wei[i][idx].second--;
            if (wei[i][idx].second == 0)
                idx++;
        }
    }

    cout << ans << endl;
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:29:42: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |         for (int j = 0; j < S / i && idx < wei[i].size(); j++)
      |                                      ~~~~^~~~~~~~~~~~~~~

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