Submission #1305967

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305967		orzorzorz	Knapsack (NOI18_knapsack)	C++20	100 / 100	57 ms	5216 KiB

knapsack

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

using namespace std;

typedef long long ll;

ll dp[2001];
// Use map to store (value -> total_count) for each weight
map<int, int> weight_groups[2001];

int main() {
    int S, N;
    scanf("%d %d", &S, &N);

    for (int i = 0; i < N; i++) {
        int v, w, k;
        scanf("%d %d %d", &v, &w, &k);
        if (w <= S) weight_groups[w][v] += k;
    }

    for (int w = 1; w <= S; w++) {
        if (weight_groups[w].empty()) continue;

        int items_taken = 0;
        int max_items = S / w;

        // Iterate values from highest to lowest
        for (auto it = weight_groups[w].rbegin(); it != weight_groups[w].rend(); ++it) {
            int v = it->first;
            int k = it->second;

            int take = min(k, max_items - items_taken);
            if (take <= 0) break;
            items_taken += take;

            // Binary splitting for the 'take' copies of value 'v' and weight 'w'
            for (int i = 1; take > 0; i <<= 1) {
                int num = min(i, take);
                ll val = (ll)num * v;
                int weight = num * w;
                for (int j = S; j >= weight; j--) {
                    dp[j] = max(dp[j], dp[j - weight] + val);
                }
                take -= num;
            }
        }
    }

    printf("%lld\n", dp[S]);
    return 0;
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:16:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |     scanf("%d %d", &S, &N);
      |     ~~~~~^~~~~~~~~~~~~~~~~
knapsack.cpp:20:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |         scanf("%d %d %d", &v, &w, &k);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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