제출 #843275

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
843275		asdf334	Knapsack (NOI18_knapsack)	C++17	73 / 100	1073 ms	3944 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define sz(x) (int)x.size()
const int MAX = 1e5;
array<ll, 3> items[MAX]; // V, W, K
ll dp[2001]; // best V for each W
int main() {
	ios_base::sync_with_stdio(false); cin.tie(nullptr);
	
	int S, N; cin >> S >> N;
	
	for (int i = 0; i < N; ++i) {
		cin >> items[i][0];
		cin >> items[i][1];
		cin >> items[i][2];
	}
	
	/*
	for (int i = 0; i < N; ++i) {
		cout << items[i][2] << " ";
	}
	*/
	
	for (int i = 0; i < N; ++i) {
		for (int pos = S; pos >= 0; --pos) {
			int max_items = min((ll)(S - pos) / items[i][1], items[i][2]);
			for (int j = 0; j <= max_items; ++j) {
				dp[pos + j * items[i][1]] = max(dp[pos + j * items[i][1]], dp[pos] + items[i][0] * j);
			}	
		}
	}
	
	ll ans = 0;
	for (int i = 0; i <= S; ++i) {
		ans = max(ans, dp[i]);
	}
	
	cout << ans << '\n';
}

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