Submission #713677

#	Time	Username	Problem	Language	Result	Execution time	Memory
713677		PanosPask	Knapsack (NOI18_knapsack)	C++14	100 / 100	65 ms	2776 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;

typedef pair<int, int> ii;


vector<ii> weight_category[MAXS + 2];
long long int bestval[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);
        weight_category[products[i].weight].push_back(make_pair(products[i].value, products[i].copies));
    }

    for (int p = 0; p <= s; p++)
        sort(weight_category[p].rbegin(), weight_category[p].rend());

    bestval[0] = 0;
    int curplace;
    for (int prod = 1; prod <= s; prod++) {
        int optimal = s / prod;
        curplace = 0;
        int proccessed = 0;
        while (curplace < weight_category[prod].size() && proccessed < optimal) {
            if (weight_category[prod][curplace].second == 0) {
                curplace++;
                continue;
            }

            proccessed++;
            int curval = weight_category[prod][curplace].first;
            weight_category[prod][curplace].second--;

            for (int i = s; i >= prod; i--)
                bestval[i] = max(bestval[i], bestval[i - prod] + curval);
        }
    }

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

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:39:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |         while (curplace < weight_category[prod].size() && proccessed < optimal) {
      |                ~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
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: 17 / 17
• Subtask 3: 20 / 20
• Subtask 4: 24 / 24
• Subtask 5: 27 / 27