Submission #975605

#	Time	Username	Problem	Language	Result	Execution time	Memory
975605		vjudge1	Knapsack (NOI18_knapsack)	C++17	0 / 100	128 ms	262144 KiB

knapsack

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

int V[100005] = {}, W[100005] = {}, K[100005] = {};
int DP[100005][2005] = {};
int solve(int N, int S) {
	if (DP[N][S] != -1)
		return DP[N][S];
	if (N == 1) {
		DP[N][S] = min(S/W[1], K[1]) * V[1];
		return DP[N][S];
	}
	int mx = 0;
	for (int k = 0; k <= K[N] && k*W[N] <= S; k++)
		mx = max(mx, solve(N - 1, S - k*W[N]) + k*V[N]);
	DP[N][S] = mx;
	return mx;
}

int main() {
	memset(DP, -1, sizeof DP);
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int S, N;
	cin >> S >> N;
	for (int i = 1; i <= N; i++)
		cin >> V[i] >> W[i] >> K[i];
	cout << solve(N, S) << '\n';
	return 0;
}

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