Submission #843291

#	Time	Username	Problem	Language	Result	Execution time	Memory
843291		asdf334	Knapsack (NOI18_knapsack)	C++17	73 / 100	1050 ms	13804 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define sz(x) (int)x.size()
const int MAX = 1e5;
ll dp[2001][MAX]; // best V for each W using the first I types of items
int main() {
	ios_base::sync_with_stdio(false); cin.tie(nullptr);
	
	int S, N; cin >> S >> N;
	
	int V, W; ll K;
	
	for (int i = 0; i < N; ++i) {
		cin >> V >> W >> K;
		
		for (int pos = S; pos >= 0; --pos) {
			int increment_pos = pos; 
			int items_used = 0;
			
			while (increment_pos <= S && items_used <= K) {
				dp[increment_pos][i + 1] = max(dp[increment_pos][i + 1], dp[pos][i] + (ll)items_used * V);
				
				increment_pos += W;
				++items_used;
			}
		}
	}
	
	ll ans = 0;
	for (int i = 0; i <= S; ++i) {
		ans = max(ans, dp[i][N]);
	}
	
	cout << ans << '\n';
}

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