Submission #649427

#	Time	Username	Problem	Language	Result	Execution time	Memory
649427		narcissus	Knapsack (NOI18_knapsack)	C++17	100 / 100	164 ms	35028 KiB

knapsack

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>

using namespace std;

int main()
{
	int s, n;
	cin >> s >> n;

	int v, w, k;
	map<int, vector<pair<int, int>>> items;
	for (int i = 0; i < n; i++) {
		cin >> v >> w >> k;
		if (w <= s) {
			items[w].push_back({v, k});
		}
	}

	int itemCnt = items.size();
	long long dp[itemCnt + 1][s + 1];
	for (int i = 0; i <= itemCnt; i++) {
		for (int j = 0; j <= s; j++) {
			dp[i][j] = (i == 0 || j == 0) ? 0 : -1;
		}
	}
	
	long long maxVal = 0, i = 1;
	for (auto item : items) {
		w = item.first;
		sort(item.second.begin(), item.second.end(), greater<pair<int, int>>());

		for (int j = 1; j <= s; j++) {
			int amnt = 0;	// cur item amnt
			int icnt = 0;	// different item count
			int tot = 0;	// total item count
			long long profit = 0;

			dp[i][j] = dp[i - 1][j];
			while ((tot + 1) * w <= j && icnt < item.second.size()) {
				tot++;
				profit += item.second[icnt].first;
				if (dp[i - 1][j - tot * w] != -1) {
					dp[i][j] = max(dp[i][j], dp[i - 1][j - tot * w] + profit);
					maxVal = max(maxVal, dp[i][j]);
				}
				amnt++;
				if (amnt == item.second[icnt].second) {
					amnt = 0;
					icnt++;
				}
			}
		}

		i++;
	}

	cout << maxVal << endl;

	return 0;
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:42:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |    while ((tot + 1) * w <= j && icnt < item.second.size()) {
      |                                 ~~~~~^~~~~~~~~~~~~~~~~~~~

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