Submission #673601

#	Time	Username	Problem	Language	Result	Execution time	Memory
673601		dayalk	Knapsack (NOI18_knapsack)	C++14	100 / 100	99 ms	35148 KiB

knapsack

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define fr(a, b) for (int i = a; i < b; i++)
#define rep(i, a, b) for (int i = a; i < b; i++)
#define mod 1000000007
#define inf (1LL << 60)
#define all(x) (x).begin(), (x).end()
#define prDouble(x) cout << fixed << setprecision(10) << x
#define triplet pair<ll, pair<ll, ll>>
#define goog(tno) cout << "Case #" << tno << ": "
#define fast_io                       \
	ios_base::sync_with_stdio(false); \
	cin.tie(NULL)
#define read(x) \
	int x;      \
	cin >> x
using namespace std;

int main()
{
	fast_io;
	int t = 1;
	// cin >> t;
	while (t--)
	{
		int s, n;
		cin >> s >> n;
		map<int, vector<pair<int, int>>> by_weight;
		fr(0, n)
		{
			int value, weight, num;
			cin >> value >> weight >> num;
			by_weight[weight].push_back({value, num});
		}
		vector<vector<ll>> best(by_weight.size() + 1, vector<ll>(s + 1, INT32_MIN));
		best[0][0] = 0;
		int at = 1;
		for (auto &[w, items] : by_weight)
		{
			sort(all(items), greater<pair<int, int>>());
			for (int i = 0; i <= s; i++)
			{
				best[at][i] = best[at - 1][i];
				int copies = 0;
				int type_at = 0;
				int curr_used = 0;
				ll profit = 0;
				while ((copies + 1) * w <= i && type_at < items.size())
				{
					copies++;
					profit += items[type_at].first;
					if (best[at - 1][i - copies * w] != INT32_MIN)
					{
						best[at][i] = max(best[at][i], best[at - 1][i - copies * w] + profit);
					}
					curr_used++;
					if (curr_used == items[type_at].second)
					{
						curr_used = 0;
						type_at++;
					}
				}
			}
			at++;
		}
		cout << *max_element(all(best.back()));
	}
	return 0;
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:39:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   39 |   for (auto &[w, items] : by_weight)
      |              ^
knapsack.cpp:49:45: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |     while ((copies + 1) * w <= i && type_at < items.size())
      |                                     ~~~~~~~~^~~~~~~~~~~~~~

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