Submission #863954

#	Time	Username	Problem	Language	Result	Execution time	Memory
863954		nguyennh	Knapsack (NOI18_knapsack)	C++14	100 / 100	70 ms	35260 KiB

knapsack

#include<bits/stdc++.h>
#define el '\n'
using namespace std ;

const int MN = 1e5 + 10 ;
const int N = 2005;
const int mod = 1e9 + 7;

mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());

map<int , vector<pair<int , int>>>weight;

int32_t main (){
//	freopen("taskname.INP", "r", stdin);
//	freopen("taskname.OUT", "w", stdout);
	ios_base::sync_with_stdio(0);
  cin.tie(0);
	int s , n;
	cin >> s >> n;
	for ( int i = 0 ; i < n ; i++ ){
		int v , w , k;
		cin >> v >> w >> k;
		if ( w <= s && k > 0 ){
			weight[w].push_back(make_pair(v , k));
		}
	}
//	for ( auto [w , item] : weight ) cout << w << " ";
	vector<vector<long long>>dp(weight.size() + 1 , vector<long long>(s + 1 , INT_MIN));
	dp[0][0] = 0;
	int id = 1;
	for ( auto [w , item] : weight ){
		sort(item.begin() , item.end() , greater<pair<int , int>>());
		for ( int j = 0 ; j <= s ; j++ ){
			dp[id][j] = dp[id - 1][j];
			long long cop = 0 , cur = 0 , val = 0 , type = 0;
			while ((cop + 1) * w <= j && type < item.size()){
				cop++;
				val += item[type].first;
				if (dp[id - 1][j - cop * w] != INT_MIN){
					dp[id][j] = max(dp[id][j] , dp[id - 1][j - cop * w] + val);
				}
				cur++;
				if (cur == item[type].second){
					cur = 0;
					type++;
				}
			}
		}
		id++;
	}
	cout << *max_element(dp.back().begin() , dp.back().end());
}

Compilation message (stderr)

knapsack.cpp: In function 'int32_t main()':
knapsack.cpp:31:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   31 |  for ( auto [w , item] : weight ){
      |             ^
knapsack.cpp:36:38: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |    while ((cop + 1) * w <= j && type < item.size()){
      |                                 ~~~~~^~~~~~~~~~~~~

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