Submission #744624

#	Time	Username	Problem	Language	Result	Execution time	Memory
744624		tibiCoder	Knapsack (NOI18_knapsack)	C++17	100 / 100	125 ms	6176 KiB

knapsack

#include <iostream>
#include <set>
#include <vector>
#include <unordered_map>
#include <climits>
#include <fstream>
#include <algorithm>

using namespace std;

#define int long long
#define MOD 1000000007
#define MAX_S 2001

#define loop3(x, vec) for (auto (x):(vec))
#define loop2(x, s, n) for (int (x) = (s); (x) < (n); ++(x))
#define loop(x, n) for (int (x) = 0; (x) < (n); ++(x))
#define inp(n, p) for (int (x) = 0; (x) < (n); ++(x)) cin >> (p)[(x)];

struct Item {
    int value;
    int weight;
    int k;

    bool operator<(const Item& other) const {
        return value > other.value;
    }
};

signed main() {
    int w, n;
    cin >> w >> n;
    vector<vector<Item>> itemsForWeight(MAX_S);
    loop(i, n) {
        Item item;
        cin >> item.value >> item.weight >> item.k;
        itemsForWeight[item.weight].emplace_back(item);
    }
    loop(i, MAX_S) {
        std::sort(itemsForWeight[i].begin(), itemsForWeight[i].end());
    }

    vector<int> dp(w+1, 0);
    vector<int> tempDp(w+1, 0);

    for (auto& items : itemsForWeight) {
        tempDp = dp;
        loop2(targetSum, 1, w+1) {
            int index = 0;
            int currentBucket = 0;
            int currentSum = 0;
            int currentValue = 0;
            while (currentBucket < items.size()) {
                currentSum += items[currentBucket].weight;
                if (currentSum > targetSum) break;
                currentValue += items[currentBucket].value;
                tempDp[targetSum] = max(tempDp[targetSum], dp[targetSum-currentSum]+currentValue);
                if (++index >= items[currentBucket].k) {
                    index = 0;
                    ++currentBucket;
                }
            }
        }
        dp = tempDp;
    }

    cout << *std::max_element(dp.begin(), dp.end()) << endl;




    return 0;
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:17:29: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   17 | #define loop(x, n) for (int (x) = 0; (x) < (n); ++(x))
      |                             ^
knapsack.cpp:34:5: note: in expansion of macro 'loop'
   34 |     loop(i, n) {
      |     ^~~~
knapsack.cpp:17:29: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   17 | #define loop(x, n) for (int (x) = 0; (x) < (n); ++(x))
      |                             ^
knapsack.cpp:39:5: note: in expansion of macro 'loop'
   39 |     loop(i, MAX_S) {
      |     ^~~~
knapsack.cpp:16:33: warning: unnecessary parentheses in declaration of 'targetSum' [-Wparentheses]
   16 | #define loop2(x, s, n) for (int (x) = (s); (x) < (n); ++(x))
      |                                 ^
knapsack.cpp:48:9: note: in expansion of macro 'loop2'
   48 |         loop2(targetSum, 1, w+1) {
      |         ^~~~~
knapsack.cpp:53:34: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<Item>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |             while (currentBucket < items.size()) {
      |                    ~~~~~~~~~~~~~~^~~~~~~~~~~~~~

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