Submission #1055401

#	Time	Username	Problem	Language	Result	Execution time	Memory
1055401		1ne	Knapsack (NOI18_knapsack)	C++14	100 / 100	89 ms	11344 KiB

knapsack

/*
*  author : Apiram                  
*  created: 12.08.2024 23:08:11
*/

#include<bits/stdc++.h>
using namespace std;
struct node{
  long long v,w,k;
};
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	long long s,n;cin>>s>>n;
	vector<node>arr(n);
	vector<vector<long long>>freq(s + 1);
	for (long long i = 0;i<n;++i){
		cin>>arr[i].v>>arr[i].w>>arr[i].k;
		vector<long long>pos;
		for (long long k = 0;;++k){
			if (arr[i].k < (1LL<<k))break;
			pos.push_back((1LL<<k));
			arr[i].k-=(1LL<<k);
		}
		if (arr[i].k != 0)pos.push_back(arr[i].k);
		for (auto x:pos){
			if (x * arr[i].w <= s){
				freq[x * arr[i].w].push_back(x * arr[i].v);
			}
		}
	}
	for (int i = 1;i<=s;++i){
		sort(freq[i].rbegin(),freq[i].rend());
		while(i * (int)freq[i].size() > s){
			freq[i].pop_back();
		}
	}
	vector<long long>dp(s + 1,0);
	dp[0] = 0;
	long long ans = 0;
	for (long long i = 1;i<=s;++i){
		for (auto x:freq[i]){
			for (long long j = s;j>=0;--j){
				if (j - i < 0)break;
				dp[j] = max(dp[j],dp[j - i] + x);
			}
		}	
		//for (int j = 0;j<=s;++j)cout<<dp[j]<<" ";
		//cout<<'\n';               
	}
	sort(dp.begin(),dp.end());
	cout<<dp.back()<<'\n';
	return 0;
}
                               

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:40:12: warning: unused variable 'ans' [-Wunused-variable]
   40 |  long long ans = 0;
      |            ^~~

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