Submission #1036049

#	Time	Username	Problem	Language	Result	Execution time	Memory
1036049		sssamui	Knapsack (NOI18_knapsack)	C++17	100 / 100	79 ms	3924 KiB

knapsack

#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int s, n;
	cin >> s >> n;

	vector<vector<pair<int, int>>> obj(s + 1);
	while (n--)
	{
		int v, w, k;
		cin >> v >> w >> k;
		obj[w].push_back({ v, k });
	}

	for (int i = 1; i <= s; i++) sort(obj[i].begin(), obj[i].end());
	vector<vector<int>> fobj(s + 1);
	for (int w = 1; w <= s; w++) while ((!obj[w].empty()) && (fobj[w].size() <= (s / w)))
	{
		fobj[w].push_back(obj[w].back().first);
		obj[w].back().second--;
		if (obj[w].back().second == 0) obj[w].pop_back();
	}

	vector<vector<int>> psums(s + 1, vector<int>(1, 0));
	for (int w = 1; w <= s; w++) for (int j = 0; j < fobj[w].size(); j++) psums[w].push_back(psums[w].back() + fobj[w][j]);
	vector<int> dp(s + 1, 0);
	for (int w = 1; w <= s; w++) for (int fw = s; fw >= w; fw--) for (int nm = 1; (nm < psums[w].size()) && (nm <= fw / w);
		nm++) dp[fw] = fmax(dp[fw], psums[w][nm] + dp[fw - w * nm]);

	cout << dp[s];
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:26:75: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   26 |  for (int w = 1; w <= s; w++) while ((!obj[w].empty()) && (fobj[w].size() <= (s / w)))
      |                                                            ~~~~~~~~~~~~~~~^~~~~~~~~~
knapsack.cpp:34:49: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |  for (int w = 1; w <= s; w++) for (int j = 0; j < fobj[w].size(); j++) psums[w].push_back(psums[w].back() + fobj[w][j]);
      |                                               ~~^~~~~~~~~~~~~~~~
knapsack.cpp:36:84: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |  for (int w = 1; w <= s; w++) for (int fw = s; fw >= w; fw--) for (int nm = 1; (nm < psums[w].size()) && (nm <= fw / w);
      |                                                                                 ~~~^~~~~~~~~~~~~~~~~

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