Submission #1309728

#	Time	Username	Problem	Language	Result	Execution time	Memory
1309728		norrawichzzz	Knapsack (NOI18_knapsack)	C++20	73 / 100	46 ms	2020 KiB

knapsack

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

bool cmp(pair<int,pair<int,int>> &a, pair<int,pair<int,int>> &b) {
	if (a.first == b.first) return a.second.first >= b.second.first;
	return a.first < b.first;
}

const int S = 2005;

int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	int W, n;
	cin>>W>> n;
	
	vector<pair<int,pair<int,int>>> a;
	for (int i=0; i<n; i++) {
		int v,w,k;
		cin>> v>> w>> k;
		a.push_back({w, {v,k}});
	}
	sort(a.begin(), a.end(), cmp);
	
	vector<pair<int,int>> e;
	int prv=a[0].first;
	
	int cnt=0;
	for (auto &x : a) {
		int w=x.first, v=x.second.first, k=x.second.second;
		if (prv != w) {
			cnt=0;
			prv = w;
		}
		for (int i=0; i<k && cnt <= S/w; i++) {
			cnt++;
			e.push_back({v, w});
		}
	}
	
	
	
	vector<int> dp(W+1, 0);
	
	for (auto &x : e) {
		for (int i=W; i>=x.second; i--) {
			dp[i] = max(dp[i],dp[i-x.second]+x.first);
		}
	}
	cout<< dp[W];
} 

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