Submission #523915

#	Time	Username	Problem	Language	Result	Execution time	Memory
523915		_karan_gandhi	Knapsack (NOI18_knapsack)	C++17	73 / 100	1060 ms	2756 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define all(v) v.begin(), v.end()
#define endl '\n'
#define pl(var) " [" << #var << ": " << (var) << "] "
#define value 0
#define weight 1
#define number 2

ll int mod = 1e9 + 7;
 
void solve() {
	int s, n; cin >> s >> n;

	vector<array<int, 3>> arr(n); 
	for (int i = 0; i < n; i++) {
		cin >> arr[i][0] >> arr[i][1] >> arr[i][2];
	}

	vector<ll int> dp(s + 1, 0);

	for (int i = 0; i < n; i++) {
		for (int j = s; j >= 1; j--) {
			// dp[j] = max(dp[j], dp[j - arr[i][weight]]);
			int cur = 1;
			// cout << pl(arr[i][weight]) << pl(arr[i][number]) << endl;
			while ((j - (arr[i][weight] * cur)) >= 0 && cur <= arr[i][number]) {
				// cout << pl(cur) << endl;
				dp[j] = max(dp[j], dp[j - arr[i][weight] * cur] + arr[i][value] * cur);
				cur++;
			}
		}
	}

	// for (auto a : dp) {
	// 	cout << a << endl;
	// }

	cout << dp[s] << endl;
}
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	// freopen("feast.in", "r", stdin);
	// freopen("feast.out", "w", stdout);
 
	// int t; cin >> t;
	// while (t--)
		solve();
 
	return 0;
}

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