Submission #1289188

#	Time	Username	Problem	Language	Result	Execution time	Memory
1289188		muhammad-ahmad	Knapsack (NOI18_knapsack)	C++20	0 / 100	1 ms	568 KiB

knapsack

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

#define int long long

const int S = 2005, N = 1e5 + 5;
int v[N], w[N], k[N], DP[12 * S][S];
vector<pair<int, int>> val[S];

signed main(){
	int s, n; cin >> s >> n;
	for (int i = 1; i <= n; i++){
		cin >> v[i] >> w[i] >> k[i];
		val[w[i]].push_back({v[i], k[i]});
	}
	
	vector<pair<int, int>> avl;
	for (int i = 1; i <= s; i++){
		sort(val[i].rbegin(), val[i].rend());
		int C = 0;
		for (auto &j : val[i]) C += j.second;
		while (val[i].size() && C - val[i].back().second >= s / i){
			C -= val[i].back().second;
			val[i].pop_back();
		}
		
		if (val[i].size()){
			val[i].back().second -= max(0ll, C - s / i);
		}
		for (auto &j : val[i]){
			for (int K = 0; K < j.second; K++) avl.push_back({i, j.first});
		}
	}
	
	n = avl.size();
	
	int ans = 0;
	
	for (int ii = 0; ii < n; ii++){
		auto [W, V] = avl[ii];
		cout << W << ' ' << V << endl;
		int i = ii + 1;
		for (int j = 0; j <= s; j++){
			DP[i][j] = DP[i - 1][j];
			if (j >= W)
				DP[i][j] = max(DP[i][j], DP[i - 1][j - W] + V);
			ans = max(ans, DP[i][j]);
		}
	}
	
	cout << ans << endl;
	
	
}

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