제출 #880865

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
880865		mertozel	Knapsack (NOI18_knapsack)	C++11	100 / 100	123 ms	4976 KiB

knapsack

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

signed main() {

	ll size, n;
	cin >> size >> n;

	vector <ll> dp(size+1, 0), weights_res[size+1];
	vector <pair<ll,ll>> weights[size+1];
	for(ll i = 0; i<n; i++) {
		ll value, weight, copy;
		cin >> value >> weight >> copy;
		weights[weight].push_back({value, copy});
	}

	for(ll i = 1; i<=size; i++) {
		sort(weights[i].begin(), weights[i].end());
		reverse(weights[i].begin(), weights[i].end());
	}

	for(ll i = 1; i <= size; i++) {
		ll cnt = 0;
		for(auto j : weights[i]) {
			for(ll k = 0; k < j.second; k++) {
				if(cnt > (2000+i-1)/i) goto here;
				weights_res[i].push_back(j.first);
				cnt++;
			}
		}
		here:;
	}

	for(ll i = 1; i<=size; i++) { //weights
		for(ll j : weights_res[i]) { // values
			for(ll k = size; k >= 0; k--) {
				dp[k] = max(dp[max(0ll, k-1)], dp[k]);
				if(k + i <= size) dp[k+i] = max(dp[k] + j, dp[k+i]);
			}
		}
	}

	cout << dp[size];


	return  0;
}

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