Submission #751052

#	Time	Username	Problem	Language	Result	Execution time	Memory
751052		hippo123	Knapsack (NOI18_knapsack)	C++17	100 / 100	61 ms	1612 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<=20; i++){
		if(list[i].size()>0) {
			cout<<"weight = "<<i<<endl;
			for (auto elem: list[i]) cout<<elem.f<<" "<<elem.s<<endl;
		}
	}
	*/
	
	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);
					}
				}
			}
		}
		//for (int j=1; j<=s; j++) cout<<dp[j]<<" ";
		//cout<<endl;
	}
	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