Submission #741946

#	Time	Username	Problem	Language	Result	Execution time	Memory
741946		abhinavshukla408	Knapsack (NOI18_knapsack)	C++14	100 / 100	97 ms	35332 KiB

knapsack

#include <iostream>
#include <vector>
#include <set>
#include <string>
#include <unordered_set>
#include <unordered_map>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
#include <cassert>
#include <math.h>
 
using namespace std;
 
using pii = pair<int,int>;
using vi = vector<int>;

#define endl "\n"
#define int int64_t 
#define pb push_back
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define FOR0(i,a) FOR(i,0,a)
#define FOR1(i,a) for (int i = (1); i <= (a); ++i)
#define TRAV(a,x) for (auto& a: x)



int32_t main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int S,N;
	cin>>S>>N;
	map<int,vector<pii>> items;
	FOR0(i,N){
		int value,weight,amt;
		cin >> value >> weight >> amt;
		if (weight <= S && amt > 0) {
			items[weight].push_back({value, amt});
		}
	}
	TRAV(i,items){
		sort(i.second.begin(),i.second.end(),greater<pii>());
	}
	vector<vector<int>> dp(items.size()+1,vector<int>(S+1,-100));
	// FOR0(i,S+1){
	// 	FOR0(j,N){
	// 		dp[i][j]=-100;
	// 	}
	// }	
	//cout<<"chp 1"<<endl;

	dp[0][0]=0;
	int at=1;

	TRAV(i,items){
		int w=i.first;
		vector<pii> item=i.second;

		FOR0(j,S+1){
			dp[at][j]=dp[at-1][j];
			int used=0;
			int type=0;
			int curTypeUsed=0;
			int profit=0;
			//cout<<"chp 1"<<endl;
				//return 1;
			while((w*(used+1))<=j && type<item.size()){
				used++;
				curTypeUsed++;
				profit+=item[type].first;
				if(dp[at-1][j-used*w]!=-100){
					dp[at][j]=max(dp[at][j],dp[at-1][j-used*w]+profit);
				}
				if(item[type].second==curTypeUsed){
					type++;
					curTypeUsed=0;
				}
			}
		}

		//return 1;
		at++;
	}
	
	int ans=-1;
	TRAV(i,dp[dp.size()-1]){
		ans=max(ans,i);
	}
	cout<<ans<<endl;

	return 0;
}

Compilation message (stderr)

knapsack.cpp: In function 'int32_t main()':
knapsack.cpp:68:33: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |    while((w*(used+1))<=j && type<item.size()){
      |                             ~~~~^~~~~~~~~~~~

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