Submission #471118

#	Time	Username	Problem	Language	Result	Execution time	Memory
471118		avijeet_03	Knapsack (NOI18_knapsack)	C++17	49 / 100	1092 ms	2048 KiB

knapsack

#include "bits/stdc++.h"
using namespace std;
#define int long long
const int mod = 1e9 + 7;

const int N = 105;
int value[N], weight[N], amount[N];

int dp[N][2005];

int calc(int i, int cap) {
	if (i == 0 or cap == 0)
		return 0;

	int &res = dp[i][cap];
	if (res != -1) return res;

	int temp = 0;
	for (int k = 0; k <= amount[i]; k++)
		if (k * weight[i] <= cap)
			temp = max(temp, k * value[i] + calc(i - 1, cap - k * weight[i]));

	return res = temp;
}

void test_case() {
	int cap, n;
	cin >> cap >> n;

	for (int i = 1; i <= n; i++)
		cin >> value[i] >> weight[i] >> amount[i];

	memset(dp, -1, sizeof(dp));
	int res = calc(n, cap);
	cout << res << "\n";
}

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	test_case();
	return 0;
}

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