Submission #1309726

#	Time	Username	Problem	Language	Result	Execution time	Memory
1309726		norrawichzzz	Knapsack (NOI18_knapsack)	C++20	37 / 100	1097 ms	33324 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;

int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	int W, n;
	cin>>W>> n;
	
	vector<pair<int,int>> a;
	for (int i=0; i<n; i++) {
		int v,w,k;
		cin>> v>> w>> k;
		for (int j=0; j<k; j++) a.push_back({v, w});
	}
	
	vector<int> dp(W+1, 0);
	
	for (auto &x : a) {
		for (int i=W; i>=x.second; i--) {
			dp[i] = max(dp[i],dp[i-x.second]+x.first);
		}
	}
	cout<< dp[W];
} 

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