Submission #1096986

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096986		hippo123	Knapsack (NOI18_knapsack)	C++17	100 / 100	45 ms	3928 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>>s>>n;
	
	vector<ll> dp(s+1, -1);
	
	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
		
		if(list[i].size()<=0) continue;   // empty weight item
 
		int weight=0; 
		
		for (int j=0; j<(int)list[i].size(); j++){ // this is the same weight, value group #
			for (int j1=0; j1<list[i][j].s && weight<=s; j1++){			
				weight+=i; // total weight until this point
				for (int k=s; k>=i; 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: 12 / 12
• Subtask 2: 17 / 17
• Subtask 3: 20 / 20
• Subtask 4: 24 / 24
• Subtask 5: 27 / 27