Submission #605308

#	Time	Username	Problem	Language	Result	Execution time	Memory
605308		Arapak	Knapsack (NOI18_knapsack)	C++17	100 / 100	249 ms	88996 KiB

knapsack

#include <bits/stdc++.h>

using namespace std;

struct ele {
	int index;
	int value;
	int weight;
	int number;
};

vector<ele> items;

int main() {
	int s,n;
	cin>>s>>n;
	vector<vector<int>> weights(s+1);
	items.resize(n);
	for(int i=0;i<n;i++) {
		items[i].index = i;
		cin>>items[i].value>>items[i].weight>>items[i].number;
	}
	
	for(auto it : items) {
		weights[it.weight].push_back(it.index);
	}
	for(int i=1;i<=s;i++) {
		sort(weights[i].begin(), weights[i].end(), [](const int a, const int b) {
			return items[a].value > items[b].value;
		});
		// for(auto it : weights[i])
		// 	cout<<it<<' ';
		// cout<<'\n';
	}
	vector<int> result(s+1);
	vector<unordered_map<int,int>> how(s+1);
	result[0] = 0;
	for(int i=1;i<=s;i++) {
		result[i] = result[i-1];
		int w = 1, ind = -1;
		// cout<<"i: "<<i<<'\n';
		for(int j=1;j<=i;j++) {
			if(weights[j].empty()) continue;
			int item_index = 0;
			int res = 0;
			for(int index : weights[j]) {
				// cout<<"		index: "<<index<<'\n';
				if(how[i-j].count(index) && how[i-j][index] >= items[index].number) continue;
				res = result[i-j] + items[index].value;
				if(res < result[i]) break;
				item_index = index;
				break;
			}
			if(res > result[i]) {
				result[i] = res;
				w = j;
				ind = item_index;
			}
		}
		how[i] = how[i-w];
		if(ind != -1)
			how[i][ind]++;
		// cout<<"i: "<<i<<" result: "<<result[i]<<'\n';
	}
	cout<<result[s]<<'\n';
}

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