Submission #1058435

#	Time	Username	Problem	Language	Result	Execution time	Memory
1058435		theehann	Knapsack (NOI18_knapsack)	C++17	29 / 100	1 ms	2652 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ft first
#define se second
#define NAME "A"
#define file freopen(NAME".INP","r",stdin); freopen(NAME".OUT","w",stdout);
#define sdf ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define el cout << "\n"
const int MOD = 1e9 + 7, N = 1e5 + 5;
int n, S, v[N], w[N], k[N], dp[N];
int32_t main(){
	sdf
	cin >> S >> n;
	for(int i = 1;i <= n;++i){
		cin >> v[i] >> w[i] >> k[i];
	}
	for(int i = 1;i <= n;++i){
		for(int s = S; s >= w[i];--s){
			int tmp = min(s / w[i], k[i]);
			dp[s] = max(dp[s], dp[s-tmp*w[i]] + v[i]*tmp);
		}
	}
	cout << dp[S];
	return 0;
}

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