Submission #483296

#	Time	Username	Problem	Language	Result	Execution time	Memory
483296		study	Knapsack (NOI18_knapsack)	C++17	100 / 100	63 ms	3788 KiB

knapsack

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

const int N = 2001;
int dp[N];
vector<pair<int,int>> wei[N];

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int s,n;
	cin >> s >> n;
	for (int i=0; i<n; ++i){
		int value,weight,nbItems;
		cin >> value >> weight >> nbItems;
		wei[weight].emplace_back(value,nbItems);
	}
	memset(dp,-1,sizeof(dp));
	dp[0] = 0;
	for (int w=1; w<=s; ++w){
		sort(wei[w].rbegin(),wei[w].rend());
		int nb = s/w;
		for (auto i:wei[w]){
			while (nb and i.second){
				for (int k=s-w; k>=0; --k){
					if (dp[k] != -1) dp[k+w] = max(dp[k+w],i.first+dp[k]);
				}
				i.second--;
				nb--;
			}
			if (nb == 0) break;
		}
	}
	int maxi = 0;
	for (int i:dp) maxi = max(maxi,i);
	cout << maxi;
	return 0;
}

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