Submission #528952

#	Time	Username	Problem	Language	Result	Execution time	Memory
528952		juankipedia	Knapsack (NOI18_knapsack)	C++14	100 / 100	86 ms	5072 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<lli> dp(S + 5, 0);

	int idx = 1;
	for(auto &[w, v] : items){
		sort(v.begin(), v.end(), greater<pair<lli, lli>>());
		vector<lli> DP;
		DP = dp;
		for(lli i = 0; i <= S; i++){
			lli k = 1, cur = 0, p = 0, used = 0;
			while((k * w) <= i && cur < v.size()){
				lli aux = i - (k * w);
				p += v[cur].first;
 				DP[i] = max(DP[i], dp[aux] + p);
				used++;
				if(used == v[cur].second) cur++, used = 0;
				k++;
			}
		}
		for(int j = 0; j < dp.size(); j++) dp[j] = max(dp[j], DP[j]);
		idx++;
	}
	lli ans = 0;
	for(int i = 0; i <= S; i++) ans = max(ans, dp[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:32:30: 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]
   32 |    while((k * w) <= i && cur < v.size()){
      |                          ~~~~^~~~~~~~~~
knapsack.cpp:41:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |   for(int j = 0; j < dp.size(); j++) dp[j] = max(dp[j], DP[j]);
      |                  ~~^~~~~~~~~~~

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