Submission #514857

#	Time	Username	Problem	Language	Result	Execution time	Memory
514857		FrostByte	Knapsack (NOI18_knapsack)	C++17	12 / 100	1 ms	356 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);
		}
	} 

	int binSearch(int v) {
		int low  = 0;
		int high = ordered_values.size() - 1;

		while( low <= high) {
			int mid = low + ((high - low) / 2);

			if (ordered_values[mid] < v) low  = mid + 1;
			else if (ordered_values[mid] > v) high = mid - 1;
			else return mid + 1;
		}

		if (high < 0)
			return 0;
		else
			if (low > (ordered_values.size() - 1))
				return ordered_values.size();
			else
				return (low < high)
					? low  + 1
					: high + 1;
	}
	void add_items(int v, int k) {
		int num_items = min(k, max_items);
		int ins_ind = 0;
		// for (; ins_ind < (int) ordered_values.size() && ordered_values[ins_ind] < v; ins_ind++) {}  //  TODO: Bin. Search
		ins_ind = binSearch(v);
		num_items = min(num_items, max_items - ins_ind);
		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;
}

Compilation message (stderr)

knapsack.cpp: In member function 'int Weight_Group::binSearch(int)':
knapsack.cpp:33:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |    if (low > (ordered_values.size() - 1))
      |        ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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