Submission #537809

#	Time	Username	Problem	Language	Result	Execution time	Memory
537809		gun_gan	Knapsack (NOI18_knapsack)	C++17	49 / 100	1090 ms	348 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];

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];
	}
	for(int i=0;i<n;i++)
	{
		for(int j=s;j>=0;j--)
		{
			for(long long k=1;k<=K[i];k++)
			{
				if(j - k * W[i] >= 0)
					dp[j] = max(dp[j], dp[j - k * W[i]] + k * V[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: 20 / 20
• Subtask 4: 0 / 24
• Subtask 5: 0 / 27