Submission #467868

#	Time	Username	Problem	Language	Result	Execution time	Memory
467868		Cxrles	Knapsack (NOI18_knapsack)	C++17	100 / 100	190 ms	34468 KiB

knapsack

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const ll INF=1e9+7;
#define f first
#define s second


int main(){
	ll limit, type;
	cin>>limit>>type;
	map<ll,vector<pair<ll,ll>>> byweight;
	for(int i=0;i<type;i++){
		ll v,w,copy;
		cin>>v>>w>>copy;
		if(w<=limit and copy>0)
		byweight[w].push_back({v,copy});
	}
	
	vector<vector<ll>>dp(byweight.size()+1,vector<ll>(limit+1,-INF));
	dp[0][0]=0;
	 ll at=1;
	for(auto &[w,item]:byweight){
		sort(item.begin(), item.end(),greater<pair<int, int>>());
		for(int i=0;i<=limit;i++){
			dp[at][i]=dp[at-1][i];
			ll copy=0;
			ll type_at=0;
			ll curr=0;
			ll profit =0;
			
			while((copy+1)*w<=i and type_at<item.size()){
				copy++;
				profit+=item[type_at].f;
				if(dp[at-1][i-copy*w]!=-INF)
				dp[at][i]=max(dp[at][i],dp[at-1][i-w*copy]+profit);
				
				curr++;
				if(curr==item[type_at].s){
					curr=0;
					type_at++;
				}
			}
		}
		at++;
	}
	
	cout<<*max_element(dp.back().begin(),dp.back().end())<<endl;
	
	
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:32:35: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |    while((copy+1)*w<=i and type_at<item.size()){
      |                            ~~~~~~~^~~~~~~~~~~~

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