Submission #510139

#	Time	Username	Problem	Language	Result	Execution time	Memory
510139		FrostByte	Knapsack (NOI18_knapsack)	C++17	73 / 100	282 ms	262148 KiB

knapsack

#include <iostream>
#include <vector>
#include <map>
using namespace std;


struct Weight_Group {
	int weight, max_items;
	vector<int> ordered_values;
	Weight_Group() : weight(0), max_items(2000) {}
	Weight_Group(int w, int v, int k, int max_weight) : weight(w), max_items(max_weight / w) {
		int num_items = min(k, max_items);
		for (int i = 0; i < num_items; i++) {
			ordered_values.push_back(v);
		}
	} 
	void add_items(int v, int k) {
		int num_items = min(k, max_items);
		for (int i = 0; i < num_items; i++) {
			ordered_values.push_back(v);
		}
		// int ins_ind = 0;
		// for (; ins_ind < (int) ordered_values.size() && ordered_values[ins_ind] < v; ins_ind++) {}  //  TODO: Bin. Search
		// for (int i = 0; i < num_items; i++) {
		// 	ordered_values.insert(ordered_values.begin() + ins_ind, v);
		// }
		// while ((int) ordered_values.size() > max_items) {
		// 	ordered_values.erase(ordered_values.begin());
		// }
	}
};


int main() {
	int max_weight, num_items;
	cin >> max_weight >> num_items;
	
	bool map_key_exists[2001] = {0};
	Weight_Group map_values[2001];
	for (int i = 0; i < num_items; i++) {
		int v, w, k;
		cin >> v >> w >> k;
		if (map_key_exists[w]) {
			map_values[w].add_items(v, k);
		} else {
			map_values[w] = Weight_Group(w, v, k, max_weight);
			map_key_exists[w] = true;
		}
	}

	int max_val_for_weight[2001] = {0};
	for (int i = 0; i <= max_weight; i++) {
		if (map_key_exists[i]) {
			for (int v : map_values[i].ordered_values) {
				for (int k = max_weight; k >= 0; k--) {
					if (k - i >= 0) {
						max_val_for_weight[k] = max(max_val_for_weight[k], max_val_for_weight[k - i] + v);
					}
				}
			}
		}
	}

	cout << max_val_for_weight[max_weight] << endl;
}

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