Submission #1259559

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259559		zurick993	Knapsack (NOI18_knapsack)	C++20	100 / 100	93 ms	17480 KiB

knapsack

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

using namespace std;

int main() {
	int s,n;cin>>s>>n;
	map<int, vector<pair<int,int>>> types;
	for (int i=0;i<n;i++) {
		int v,w,k;
		cin>>v>>w>>k;
		types[w].push_back({v,k});
	}
	vector<vector<int>> best(types.size()+1, vector<int>(s+1, 0));
	auto curr_type_it = begin(types);
	for (size_t i = 1; i <= types.size(); i++) {
		auto curr_weight = curr_type_it->first;
		auto& curr_type = curr_type_it->second;
		sort(begin(curr_type), end(curr_type), greater<>());

		for (int w = 0; w <= s; w++) {
			best[i][w] = best[i-1][w];
			int profit = 0;
			size_t idx=0;
			int used=0;
			for (int j = 1; idx<curr_type.size() && w-j*curr_weight >= 0; j++) {
				if (used == curr_type[idx].second) {
					idx++;
					used =0;
				}
				if (idx >= curr_type.size())
					break;
				profit += curr_type[idx].first;
				used++;
				best[i][w] = max(best[i][w], profit + best[i-1][w-j*curr_weight]);
			}
		}
		curr_type_it = next(curr_type_it);
	}
	cout << *max_element(begin(best[types.size()]), end(best[types.size()])) << endl;
}

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