Submission #318711

#	Time	Username	Problem	Language	Result	Execution time	Memory
318711		ryangohca	Knapsack (NOI18_knapsack)	C++17	100 / 100	145 ms	5228 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
priority_queue<pii> values[2001];
vector<pii> candidates;
int dp[2001];
int32_t main() {
    int s, n; cin >> s >> n;
    for (int i = 0; i < n; i++){
        int v, w, k; cin >> v >> w >> k;
        values[w].push({v, k});
    }
    for (int i = 1; i <= 2000; i++){
        int canChoose = s / i;
        while (!values[i].empty() && canChoose > 0){
            pii top_e = values[i].top(); values[i].pop();
            int num_chosen = min(canChoose, top_e.second);
            for (int j = 0; j < num_chosen; j++) candidates.push_back({top_e.first, i});
            canChoose -= num_chosen;
        }
    }
    for (int a = 0; a < candidates.size(); ++a){
        for (int c = s; c >= candidates[a].second; --c){
            dp[c] = max(dp[c], dp[c - candidates[a].second] + candidates[a].first);
        }
    }
    cout << dp[s] << '\n';
}

Compilation message (stderr)

knapsack.cpp: In function 'int32_t main()':
knapsack.cpp:23:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int>, std::allocator<std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |     for (int a = 0; a < candidates.size(); ++a){
      |                     ~~^~~~~~~~~~~~~~~~~~~

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