Submission #967847

#	Time	Username	Problem	Language	Result	Execution time	Memory
967847		hippo123	Knapsack (NOI18_knapsack)	C++17	73 / 100	1060 ms	3864 KiB

knapsack

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

struct d1{
	int v, w, k;
	double r;
};

bool comp(d1 a, d1 b){
	if(a.r==b.r) return a.w<b.w;
	return a.r>b.r;
}

int main(){
	int s, n; cin>>s>>n;
	
	vector<d1> d(n);
	
	for (int i=0; i<n; i++) {
		cin>>d[i].v>>d[i].w>>d[i].k;
		d[i].r=double(d[i].v)/d[i].w;
	}
	sort(d.begin(), d.end(), comp);
	
	vector<ll> dp(s+1, -1);
	dp[0]=0;
	
	for (int i=0; i<n; i++){
		for (int x=s; x>=0; x--){
			if(dp[x]>=0){
				for (int j=0; j<d[i].k && x+(j+1)*d[i].w<=s; j++){
					dp[x+(j+1)*d[i].w]=max(dp[x]+(j+1)*d[i].v, dp[x+(j+1)*d[i].w]);
				}
			}
		}
	}
	ll ans=0;
	for (int i=0; i<=s; i++) ans=max(ans, dp[i]);
	cout<<ans<<endl;
	
}

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