제출 #744620

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
744620		tibiCoder	Knapsack (NOI18_knapsack)	C++17	컴파일 에러	0 ms	0 KiB

knapsack

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

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, 0);
    vector<int> tempDp(w, 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[index].weight;
                if (currentSum > targetSum) break;
                currentValue += items[index].value;
                tempDp[targetSum] = max(tempDp[targetSum], dp[targetSum-currentSum]+currentValue);
                if (++index >= items[currentBucket].k) ++currentBucket;
            }
        }
        dp = tempDp;
    }

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




    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

knapsack.cpp: In function 'int main()':
knapsack.cpp:16:29: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   16 | #define loop(x, n) for (int (x) = 0; (x) < (n); ++(x))
      |                             ^
knapsack.cpp:33:5: note: in expansion of macro 'loop'
   33 |     loop(i, n) {
      |     ^~~~
knapsack.cpp:16:29: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   16 | #define loop(x, n) for (int (x) = 0; (x) < (n); ++(x))
      |                             ^
knapsack.cpp:38:5: note: in expansion of macro 'loop'
   38 |     loop(i, MAX_S) {
      |     ^~~~
knapsack.cpp:39:14: error: 'sort' is not a member of 'std'
   39 |         std::sort(itemsForWeight[i].begin(), itemsForWeight[i].end());
      |              ^~~~
knapsack.cpp:15:33: warning: unnecessary parentheses in declaration of 'targetSum' [-Wparentheses]
   15 | #define loop2(x, s, n) for (int (x) = (s); (x) < (n); ++(x))
      |                                 ^
knapsack.cpp:47:9: note: in expansion of macro 'loop2'
   47 |         loop2(targetSum, 1, w+1) {
      |         ^~~~~
knapsack.cpp:52:34: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<Item>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |             while (currentBucket < items.size()) {
      |                    ~~~~~~~~~~~~~~^~~~~~~~~~~~~~
knapsack.cpp:63:19: error: 'max_element' is not a member of 'std'; did you mean 'tuple_element'?
   63 |     cout << *std::max_element(dp.begin(), dp.end()) << endl;
      |                   ^~~~~~~~~~~
      |                   tuple_element