Submission #713651

#	Time	Username	Problem	Language	Result	Execution time	Memory
713651		PanosPask	Knapsack (NOI18_knapsack)	C++14	0 / 100	2 ms	340 KiB

knapsack

#include <bits/stdc++.h>
#define MAXN 100000
#define MAXS 2000

using namespace std;

struct item {
    int copies;
    int value;
    int weight;
};
typedef struct item Item;

int latest[MAXS + 2];
int latest_val[MAXS + 2];
int used[MAXS + 2];
long long int bestval[MAXS + 2];
int n, s;
Item products[MAXN + 2];

int main(void)
{
    scanf("%d %d", &n, &s);
    for (int i = 0; i < n; i++)
        scanf("%d %d %d", &products[i].value, &products[i].weight, &products[i].copies);

    bestval[0] = 0;
    for (int i = 0; i < n; i++) {
        Item curitem = products[i];
        memset(used, 0, sizeof(used));

        for (int i = products[i].weight; i <= s; i++) {
            if (used[i - curitem.weight] < curitem.copies) {
                bestval[i] = bestval[latest[i]] + latest_val[i];
                used[i] = used[latest[i]];

                if (bestval[i - curitem.weight] + curitem.value > bestval[i]) {
                    used[i] = used[i - curitem.weight] + 1;
                    latest[i] = i - curitem.weight;
                    latest_val[i] = curitem.value;
                    bestval[i] = bestval[i - curitem.weight] + curitem.value;
                }
            }
        }
    }

    for (int i = 0; i <= s; i++)
        bestval[s] = max(bestval[s], bestval[i]);

    printf("%lld\n", bestval[s]);
    return 0;
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:23:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |     scanf("%d %d", &n, &s);
      |     ~~~~~^~~~~~~~~~~~~~~~~
knapsack.cpp:25:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |         scanf("%d %d %d", &products[i].value, &products[i].weight, &products[i].copies);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
knapsack.cpp:32:18: warning: 'i' may be used uninitialized in this function [-Wmaybe-uninitialized]
   32 |         for (int i = products[i].weight; i <= s; i++) {
      |                  ^

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