Submission #528681

#	Time	Username	Problem	Language	Result	Execution time	Memory
528681		juankipedia	Knapsack (NOI18_knapsack)	C++14	73 / 100	131 ms	262148 KiB

knapsack

# include <bits/stdc++.h>
using namespace std;
/*************************************************************************************/
# define endl "\n"
# define io_boost std::ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
typedef unsigned long long int ulli;
typedef long long int lli; 
/*************************************JUANKIPEDIA*************************************/
const lli oo = INT32_MIN;
const int MAXN = 100005;
lli N, S;

int main(){
    io_boost;
	cin >> S >> N;
	map<lli, vector<pair<lli, lli>>> items;
	for(lli i = 0; i < N; i++){
		lli V, W, K;
		cin >> V >> W >> K;
		if(W <= S) items[W].push_back({V, K});
	}

	vector<vector<lli>> dp(N + 5, vector<lli>(S + 5, oo));
	dp[0][0] = 0;
	int idx = 1;
	for(auto &[w, v] : items){
		sort(v.begin(), v.end(), greater<pair<lli, lli>>());
		for(lli i = 0; i <= S; i++){
			dp[idx][i] = dp[idx - 1][i];
			lli k = 0, cur = 0, p = 0, used = 0;
			while(((k + 1) * w) <= i && cur < v.size()){
				k++;
				lli aux = i - (k * w);
				p += v[cur].first;
				if(dp[idx - 1][aux] != oo)
 					dp[idx][i] = max(dp[idx][i], dp[idx - 1][aux] + p);
				
				used++;
				if(used == v[cur].second){
					cur++;
					used = 0;
				}
			}
		}
		idx++;
	}
	lli ans = 0;
	for(int i = 0; i <= S; i++) ans = max(ans, dp[idx - 1][i]);
	cout << ans << endl;
	return 0;
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:26:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   26 |  for(auto &[w, v] : items){
      |            ^
knapsack.cpp:31:36: warning: comparison of integer expressions of different signedness: 'lli' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |    while(((k + 1) * w) <= i && cur < v.size()){
      |                                ~~~~^~~~~~~~~~

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