Submission #548991

#	Time	Username	Problem	Language	Result	Execution time	Memory
548991		alexz1205	Knapsack (NOI18_knapsack)	C++14	37 / 100	1063 ms	324 KiB

knapsack

#include <iostream>
using namespace std;

int main() {
	int s, n;
	cin >> s >> n;
	long long int data[n][3], dp[s+1], next[s+1];
	for (int x = 0; x < n; x ++){
		cin >> data[x][0] >> data[x][1] >> data[x][2];
	}
	for (int x = 0; x <= s; x ++){
		dp[x] = next[x] = 0;
	}
	for (int a = 0; a < n; a ++){
		int c = data[a][0], w = data[a][1], k = data[a][2];
		for (int b = 0; b < k; b ++){
			for (int x = w; x <= s; x ++){
				next[x] = max(max(dp[x], dp[x-w] + c), next[x-1]);
			}
			for (int x = w; x <= s; x ++){
				dp[x] = next[x];
			}
		}
	}
	cout << dp[s] << endl;
	return 0;
}

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