Submission #505109

#	Time	Username	Problem	Language	Result	Execution time	Memory
505109		hkim	Knapsack (NOI18_knapsack)	C++14	100 / 100	123 ms	4828 KiB

knapsack

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int S, N;
int V[100005], W[100005], K[100005];
vector<pair<int, int>> weights[2005];
int dp[2005];

int main() {
    cin >> S >> N;
    for (int i = 0; i < N; i++) {
        cin >> V[i] >> W[i] >> K[i];
        weights[W[i]].emplace_back(make_pair(V[i], K[i]));
    }

    for (int i = 0; i <= S;  i++) {
        if (weights[i].empty()) continue;
        sort(weights[i].begin(), weights[i].end(), greater<>());
        int weight_idx = 0;
        for (int j = 0; j * i < S; j++) {
            if (weight_idx >= weights[i].size()) break;
            for (int k = S; k >= i; k--) {
                dp[k] = max(dp[k], dp[k - i] + weights[i][weight_idx].first);
            }
            weights[i][weight_idx].second--;
            if (weights[i][weight_idx].second == 0) weight_idx++;
        }
    }

    cout << dp[S] << endl;

    for (int i = 0; i <= S; i++) {
        //cout << dp[i] << " ";
    }
    //cout << endl;

    return 0;
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:24:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |             if (weight_idx >= weights[i].size()) break;
      |                 ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~

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