Submission #860087

#	Time	Username	Problem	Language	Result	Execution time	Memory
860087		pete555	Knapsack (NOI18_knapsack)	C++17	100 / 100	136 ms	35156 KiB

knapsack

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define s second
#define f first
int main(){
	int s, n; 
	cin >> s >> n;
	map<int, vector<pair<int,int>>> items;
	for(int i=0; i<n; i++){
		int v, w, k; cin >> v >> w >> k;
		items[w].push_back({v, k});
	}
	vector<vector<ll>> dp(items.size()+1, vector<ll>(s+1));
	dp[0][0] = 0;
	int at = 1;
	for(auto item: items){
		sort(item.s.begin(), item.s.end(), greater<pair<int,int>>());
		for(int i=0; i<=s; i++){
			dp[at][i] = dp[at-1][i];
			int copy = 0, type_at = 0, curr_used = 0;
			ll profit = 0;
			while((copy+1)*item.first <= i and type_at < item.s.size()){
				copy++;
				profit += item.s[type_at].f;
				dp[at][i] = max(dp[at][i], dp[at-1][i-copy*item.f] + profit);
				
				curr_used++;
				if(curr_used == item.s[type_at].s){
					curr_used = 0;
					type_at++;
				}
			}
		}
		at++;
	}
	cout << dp[items.size()][s];
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:23:47: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |    while((copy+1)*item.first <= i and type_at < item.s.size()){
      |                                       ~~~~~~~~^~~~~~~~~~~~~~~

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