Submission #1117998

#	Time	Username	Problem	Language	Result	Execution time	Memory
1117998		classic	Knapsack (NOI18_knapsack)	C++14	100 / 100	61 ms	3952 KiB

knapsack

#include <bits/stdc++.h>

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	int limitWeight, numItem;
	std::cin >> limitWeight >> numItem;
	std::vector<std::array<int, 3>> items;
	for (int index = 0; index < numItem; index++) {
		int value, weight, amount;
		std::cin >> value >> weight >> amount;
		items.push_back({weight, value, amount});
	}
	sort(items.begin(), items.end(), [](const std::array<int, 3> &leftSide, const std::array<int, 3> &rightSide) {
		if (leftSide[0] == rightSide[0]) {
			return leftSide[1] > rightSide[1];
		}
		return leftSide[0] < rightSide[0];
	});
	std::vector<int> weightItem, valueItem;
	std::vector<int> countItemWeight(limitWeight + 1);
	for (const auto &[weight, value, amount] : items) {
		int total = limitWeight / weight;
		int index = 0;
		while (countItemWeight[weight] < total && index < amount) {
			countItemWeight[weight]++;
			index++;
			weightItem.emplace_back(weight);
			valueItem.emplace_back(value);
		}
	}
	std::vector<int> maxValue(limitWeight + 1);
	for (int index = 0; index < (int)weightItem.size(); index++) {
		for (int weight = limitWeight; weight > 0; weight--) {
			if (weight >= weightItem[index]) {
				maxValue[weight] = std::max(maxValue[weight], maxValue[weight - weightItem[index]] + valueItem[index]);
			}
		}
	}
	int result = 0;
	for (int weight = 0; weight <= limitWeight; weight++) {
		result = std::max(result, maxValue[weight]);
	}
	std::cout << result;
	return 0;
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:22:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   22 |  for (const auto &[weight, value, amount] : items) {
      |                   ^

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