Submission #692513

#	Time	Username	Problem	Language	Result	Execution time	Memory
692513		TAhmed33	Knapsack (NOI18_knapsack)	C++98	0 / 100	95 ms	262144 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
int w, n;
int copies[100001] = {};
int arr[100001][2] = {};
int dp[100001][2001] = {};
int ans (int pos, int cur) {
	int &ret = dp[pos][cur];
	if (ret != -1) return ret;
	if (pos == 0 || cur == 0) return ret = 0;

	if (arr[pos][0] > cur) {
		return ret = ans(pos - 1, cur);
	}
	int p = ans(pos - 1, cur);
	for (int i = 1; arr[pos][0] * i <= cur && i <= copies[pos]; i++) {
		p = max(p, i * arr[pos][1] + ans(pos - 1, cur - i * arr[pos][0]));
	}
	return ret = p;
}
int main () {
	memset(dp, -1, sizeof(dp));
	cin >> w >> n;
	for (int i = 1; i <= n; i++) {
		cin >> arr[i][1] >> arr[i][0] >> copies[i];
	}
	cout << ans(n, w) << endl;
}

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