Submission #713660

#	Time	Username	Problem	Language	Result	Execution time	Memory
713660		PanosPask	Knapsack (NOI18_knapsack)	C++14	12 / 100	1 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];
bool reached[MAXS + 2];
int n, s;
Item products[MAXN + 2];

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

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

        for (int i = curitem.weight; i <= s; i++) {
                bestval[i] = bestval[latest[i]] + latest_val[i];
                used[i] = used[latest[i]];
            if (used[i - curitem.weight] < curitem.copies && reached[i - curitem.weight]) {
                if (bestval[i - curitem.weight] + curitem.value > bestval[i]) {
                    used[i] = used[i - curitem.weight] + 1;
                    reached[i] = true;
                    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:24:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |     scanf("%d %d", &s, &n);
      |     ~~~~~^~~~~~~~~~~~~~~~~
knapsack.cpp:26:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |         scanf("%d %d %d", &products[i].value, &products[i].weight, &products[i].copies);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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