Submission #751049

#	Time	Username	Problem	Language	Result	Execution time	Memory
751049		hippo123	Knapsack (NOI18_knapsack)	C++17	0 / 100	1 ms	340 KiB

knapsack

#include <bits/stdc++.h>

using namespace std;
#define ll long long
#define pr pair<int, int>
#define f first
#define s second

ll n, s;

bool cmp(pr a, pr b){
	return a.f> b.f;
}



int main(){

	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n>>s;
	
	vector<ll> dp(s+1, LLONG_MIN);
	
	vector<vector<pr>> list(2001);
	
	for (int i=0; i<=n; i++){
		int vi, wi, ki; cin>>vi>>wi>>ki;
		list[wi].push_back({vi, ki});
	}
	// sort the items per values from top to bottom with the same weight
	for (int i=1; i<=s; i++){
		if(list[i].size()>0) sort(list[i].begin(), list[i].end(), cmp);
	}
	// now using the standard knapsack to calculate the problem
	dp[0]=0;
	
	
	for (int i=1; i<=s; i++){ // convert to weight dim
		int weight=0; 
		
		if(!(list[i].size()>0)) continue;   // empty weight item
		
		for (int j=0; j<(int) list[i].size() && weight<=s; j++){ // # of items ki but it should be also limited to s weight
			weight+=i; // total weight until this point
			for (int k=s; k>=0; k--){
				if(dp[k-i]>=0 ) {
					dp[k]=max(dp[k], dp[k-i]+list[i][j].f);
				}
			}
		}
	}
	ll mval=0;
	for (int i=0; i<=s; i++) mval=max(mval, dp[i]);
	cout<<mval;
	

}

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