Submission #611693

#	Time	Username	Problem	Language	Result	Execution time	Memory
611693		abcisosm5	Knapsack (NOI18_knapsack)	C++17	100 / 100	65 ms	3832 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;

int S, N;
const int MS = 2001;
vector<pair<int,int>> items[MS]; //items[w] contains {-v,k}
vector<pair<int,int>> final_items; //contains {w, v}
int dp[MS] = {};

int main(){
	cin.tie(0)->sync_with_stdio(0);

	cin >> S >> N;

	for(int i = 0; i < N; i++){
		int v, w, k; cin >> v >> w >> k;
		if(w <= S){
			items[w].push_back({-v,k});
		}
	}

	//we only need to consider the first floor(S/w) items of weight w
	for(int w = 0; w <= S; w++){
		sort(items[w].begin(), items[w].end());
		int total = 0; 
		for(pair<int,int> p : items[w]){
			int v = -p.first; int k = p.second;
			if(total + k < S/w){
				for(int i = 0; i < k; i++) final_items.push_back({w, v});
				total += k;
			} else if(total < S/w){
				for(int i = 0; i < S/w-total; i++) final_items.push_back({w, v});
				break;
			}
		}
	}

	//now, a classic knapsack dp:
	for(pair<int,int> p : final_items){
		int w = p.first; int v = p.second;
		for(int i = S; i >= w; i--){
			dp[i] = max(dp[i], dp[i-w] + v);
		}
	}

	cout << dp[S];

	return 0;
}

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