Submission #523922

#	Time	Username	Problem	Language	Result	Execution time	Memory
523922		_karan_gandhi	Knapsack (NOI18_knapsack)	C++17	73 / 100	1095 ms	3520 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() {
	ll int s, n; cin >> s >> n;

	vector<array<ll int, 3>> arr; 
	for (int i = 0; i < n; i++) {
		int a, b, c; cin >> a >> b >> c;
		if (b > s) continue;
		arr.push_back({a, b, c});
	}

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

	for (int i = 0; i < n; i++) {
		for (int j = s; j >= 1; j--) {
			ll int cur = 1;
			// here I will have O(s^2) making the total complexity O(N * S^2)
			while ((j - (arr[i][weight] * cur)) >= 0 && cur <= arr[i][number]) { 
				dp[j] = max(dp[j], 
							dp[j - arr[i][weight] * cur] + arr[i][value] * cur);
				cur++;
			}
		}
	}

	cout << dp[s] << endl;
}
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
 
	// 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