Submission #598706

#	Time	Username	Problem	Language	Result	Execution time	Memory
598706		sshoney1	Knapsack (NOI18_knapsack)	C++17	73 / 100	626 ms	262144 KiB

knapsack

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

const int N = 100000;
const int S = 2000;

long long int v[N + 1], w[N + 1], k[N + 1], s, n, dp[N + 1][S + 1];

long long int f(int cur_ind, int cur_w){
	if(cur_ind > n) return 0;
	
	if(dp[cur_ind][cur_w] != -1) return dp[cur_ind][cur_w];
	
	long long int a = 0;
	
	for(long long int i = 0; i <= k[cur_ind]; i++){
		if(cur_w + i*w[cur_ind] <= s){
			a = max(a, f(cur_ind + 1, cur_w + i*w[cur_ind]) + v[cur_ind]*i);
		}
		else{
			break;
		}
	}	
	
	return dp[cur_ind][cur_w] = a;
}

int main(){
	
	cin >> s >> n;
	
	for(int i = 1; i <= n; i++){	
		cin >> v[i] >> w[i] >> k[i]; 
		for(int j = 0; j <= s; j++){
			dp[i][j] = -1;
		}
	}
	
	cout << f(1, 0);
	
	return 0;
}

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