Submission #537816

#	Time	Username	Problem	Language	Result	Execution time	Memory
537816		gun_gan	Knapsack (NOI18_knapsack)	C++17	29 / 100	2 ms	340 KiB

knapsack

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

const int N = 1e5, S = 2e3 + 1;

long long V[N], W[N], K[N], n, s, dp[S], ord[N];
template <typename T> void ckmax(T &a, T b) { a = max(a, b); }

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

	cin >> s >> n;	
	if(n == 1)
	{
		cin >> V[0] >> W[0] >> K[0];
		cout << min(K[0], s / W[0]) * V[0];
		return 0;
	}
	for(int i=0;i<n;i++)
	{
		cin >> V[i] >> W[i] >> K[i];
	}
	iota(ord, ord + n, 0);
	sort(ord, ord + n, [&](int a, int b){ // larger V[i] / W[i]
		return V[a] * W[b] > V[b] * W[a];
	});
	for(int i=0;i<n;i++)
	{
		for(int j=s;j>=0;j--)
		{
			int take = min(K[ord[i]], (s - j) / W[ord[i]]);
			ckmax(dp[j + take * W[ord[i]]], dp[j] + take * V[ord[i]]);
		}
	}
	// for(int i=0;i<=20;i++){
	// 	cout << i << ": " << dp[i] << "\n";
	// }
	cout << *max_element(dp, dp + s + 1);

}

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