제출 #1059402

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1059402		theehann	Knapsack (NOI18_knapsack)	C++17	100 / 100	68 ms	36432 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ft first
#define se second
#define NAME "A"
#define file freopen(NAME".INP","r",stdin); freopen(NAME".OUT","w",stdout);
#define sdf ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define el cout << "\n"
const int MOD = 1e9 + 7, N = 1e5 + 5;
int n, S;
int32_t main(){
	sdf
	cin >> S >> n;
	map<int, vector<pair<int, int>>> by_weight;
	for(int i = 1;i <= n;++i){
		int v, w, k;
		cin >> v >> w >> k;
		by_weight[w].push_back({v, k});
	}
	int in = 1, ans = 0 ;
	vector<vector<int>> dp(by_weight.size() + 2, vector<int>(S+10, -1e17));
	dp[0][0] = 0;
	for(auto &[w, a] : by_weight){
		sort(a.begin(), a.end(), greater<pair<int, int>>());
		for(int j = 0;j <= S;++j){
			dp[in][j] = dp[in-1][j];
			int c = 0, cur = 0, cur_used = 0;
			unsigned int id = 0;
			while((c + 1) * w <= j && id < a.size()){
				cur += a[id].ft;
				c++;
				dp[in][j] = max(dp[in][j], dp[in-1][j-c*w] + cur);
				ans = max(ans, dp[in][j]);
				cur_used++;
				if(cur_used == a[id].se){
					cur_used = 0;
					id++;
				}
			}
		}
		in++;
	}
	cout << ans;
	return 0;
}

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