제출 #1055358

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1055358		1ne	Knapsack (NOI18_knapsack)	C++14	17 / 100	1 ms	348 KiB

knapsack

/*
*  author : Apiram                  
*  created: 12.08.2024 23:08:11
*/

#include<bits/stdc++.h>
using namespace std;
struct node{
  long long v,w,k;
};
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	long long s,n;cin>>s>>n;
	vector<node>arr(n);
	for (long long i = 0;i<n;++i){
		cin>>arr[i].v>>arr[i].w>>arr[i].k;
	}
	vector<long long>dp(s + 1,-1);
	dp[0] = 0;
	long long ans = 0;
	for (long long i = 0;i<n;++i){
		vector<long long>pos;
		vector<long long>new_dp = dp;
		for (long long k = 0;;++k){
			if (arr[i].k < (1<<k))break;
			pos.push_back((1<<k));
			arr[i].k-=(1<<k);
		}
		if (arr[i].k != 0)pos.push_back(arr[i].k);
		sort(pos.begin(),pos.end());
		for (long long j = s;j>=0;--j){
			if (dp[j] == -1)continue;
			for (auto x:pos){
				if (j + x * arr[i].w > s)break;
				dp[j + x * arr[i].w] = max(dp[j + x * arr[i].w],dp[j] + arr[i].v * x);
			}
			ans = max(ans,dp[j]);	
		}               
	}
	sort(dp.begin(),dp.end());
	cout<<dp.back()<<'\n';
	return 0;
}

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