Submission #785641

#	Time	Username	Problem	Language	Result	Execution time	Memory
785641		0x34c	Knapsack (NOI18_knapsack)	C++17	100 / 100	106 ms	2144 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<int> vl, wi;

    for (int i = 1; i <= S; i++)
    {
        int idx = 0;
        for (int j = 0; j < S / i && idx < wei[i].size(); j++)
        {
            vl.push_back(wei[i][idx].first);
            wi.push_back(i);
            wei[i][idx].second--;
            if (wei[i][idx].second == 0)
                idx++;
        }
    }

    ll dp[2][S + 1];
    int fr = 0, sc = 1;
    dp[0][0] = 0;

    for (int j = 1; j <= S; j++)
    {
        dp[0][j] = 0;
        if (wi[0] <= j)
            dp[0][j] = vl[0];
    }

    for (int i = 1; i < vl.size(); i++)
    {
        for (int j = 0; j <= S; j++)
        {
            dp[sc][j] = dp[fr][j];
            if (wi[i] <= j)
                dp[sc][j] = max(dp[sc][j], dp[fr][j - wi[i]] + vl[i]);
        }
        swap(fr, sc);
    }

    cout << dp[fr][S] << 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++)
      |                                      ~~~~^~~~~~~~~~~~~~~
knapsack.cpp:50:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |     for (int i = 1; i < vl.size(); i++)
      |                     ~~^~~~~~~~~~~

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