Submission #695240

#	Time	Username	Problem	Language	Result	Execution time	Memory
695240		TAhmed33	Knapsack (NOI18_knapsack)	C++98	100 / 100	166 ms	19564 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
vector <vector <pair <int, int>>> arr(2001);
int n, W; 
bool compare (pair <int, int> a, pair <int, int> b) {
	return a.first > b.first; //value
}
int dp[2001][2001];
int ans (int pos, int weight) {
	int &ret = dp[pos][weight];
	if (ret != -1) return ret;
	if (weight == 0 || pos == 0) return ret = 0;
	int sum = 0;
	int w = 0;
	int pp = ans(pos - 1, weight);
	for (auto i : arr[pos]) {
		int val = i.first;
		int amnt = i.second;
		while (amnt--) {
			sum += val;
			w += pos;
			if (w > weight) {
				return ret = pp;
			}
			pp = max(pp, sum + ans(pos - 1, weight - w));
		}
	}
	return ret = pp;
}
int main () {
	memset (dp, -1, sizeof(dp));
	cin >> W >> n;
	for (int i = 1; i <= n; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		arr[b].push_back({a, c});
	}
	for (int i = 1; i <= 2000; i++) {
		sort(arr[i].begin(), arr[i].end(), compare);
	}
	cout << ans(2000, W) << endl;
}

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