Submission #630646

#	Time	Username	Problem	Language	Result	Execution time	Memory
630646		chjiao	Knapsack (NOI18_knapsack)	C++14	100 / 100	112 ms	1812 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
#define ll long long

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    //freopen("Knapsack.in", "r", stdin);
    // freopen("Knapsack.out", "w", stdout);

	int limit, type_num;
	cin >> limit >> type_num;
	
	map<int, vector<pair<int, int>>> by_weight; 			
    //vector<vector<int>> items(type_num, vector<int>(3));
	for (int t = 0; t < type_num; t++) {
		int value, weight, amt;
		cin >> value >> weight >> amt;
		if (weight <= limit && amt > 0) {
			by_weight[weight].push_back({value, amt});
		}
	}
    vector<int> dp(limit+1, -1);
    dp[0]= 0;

	int dylimit = 0;
	for (auto& [w, items] : by_weight) {
		// sort items in reverse order by value
		sort(items.begin(), items.end(), greater<pair<int, int>>());
		for(int i = dylimit; i>=0; i--) {
			if(dp[i]<0) continue;
			int curr = i;
			bool withinLimit = true;
			for (auto& item:items){
				for (int k=1; k<=item.second; k++) {
					if (curr+k*w>limit) {
						withinLimit = false;
						break;
					}
					dp[curr+k*w] = max(dp[curr+k*w], dp[curr] + k*item.first);
					dylimit = max(dylimit, curr+k*w);
				}
				if(!withinLimit) break;
				curr += w*item.second;
			}
		}
	}

    cout << *max_element(dp.begin(), dp.end()) << endl;
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:26:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   26 |  for (auto& [w, items] : by_weight) {
      |             ^

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