제출 #514881

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
514881		FrostByte	Knapsack (NOI18_knapsack)	C++17	73 / 100	1085 ms	344 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 len = (int) ordered_values.size();
		int low  = 0;
		int high = len - 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 > (len - 1))
				return len;
			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 - 1);
		// 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;
}

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