Submission #1269374

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269374		aliabadi	Knapsack (NOI18_knapsack)	C++20	100 / 100	130 ms	1668 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
#define ll long long int
const int MINF = -1e9 , MAXN = 2e3 + 10;
vector<pair<int,int>> vec[MAXN];
vector<int> dp(MAXN);
int main(){
	int s , n , ans = 0;
	cin >> s >> n;
	for(int i = 1; i <= n; i++){
		int v , w , c;
		cin >> v >> w >> c;
		vec[w].push_back({v , c});
	}
	for(int i = 1; i <= s; i++) dp[i] = MINF;
	for(int i = 1; i <= s; i++){
		sort(begin(vec[i]) , end(vec[i]));
		int ma = s / i;
		while(vec[i].size() > 0 and ma > 0){
			auto [v , c] = vec[i].back();
			vec[i].pop_back();
			for(int j = s; j >= i; j--) dp[j] = max(dp[j - i] + v , dp[j]);
			if(c - 1 > 0) vec[i].push_back({v , c - 1});
			ma--;
		}
		ans = max(ans , dp[i]);
	}
	cout << ans;
}

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