Submission #1241710

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241710		badge881	Knapsack (NOI18_knapsack)	C++20	73 / 100	1095 ms	2632 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
#define ll long long

const ll MAX_CAP = 2007;
const ll MAX_ITEMS = 1e5 + 7;

ll values[MAX_ITEMS], weights[MAX_ITEMS], quantities[MAX_ITEMS];
ll dp[MAX_CAP];

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

    for (int i = 0; i < N; i++) {
        scanf("%lld %lld %lld", &values[i], &weights[i], &quantities[i]);
    }

    memset(dp, 0, sizeof(dp));

    for (int i = 0; i < N; i++) {
        ll v = values[i], w = weights[i], q = quantities[i];

        // Binary decomposition of q
        for (ll k = 1; q > 0; k <<= 1) {
            ll take = min(k, q);
            ll totalW = take * w;
            ll totalV = take * v;

            for (ll cap = S; cap >= totalW; cap--) {
                dp[cap] = max(dp[cap], dp[cap - totalW] + totalV);
            }

            q -= take;
        }
    }

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

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:13:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |     scanf("%lld %lld", &S, &N);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~
knapsack.cpp:16:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |         scanf("%lld %lld %lld", &values[i], &weights[i], &quantities[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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