Submission #1213280

#	Time	Username	Problem	Language	Result	Execution time	Memory
1213280		shrek_lover	Knapsack (NOI18_knapsack)	C++20	37 / 100	1094 ms	328 KiB

knapsack

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

long long dp[2020], sp[2020];
int N, S;

int main() {
	cin >> S >> N;
	for(int i = 0; i < N; i++) {
		int p, w, n;
		cin >> p >> w >> n;
		swap(dp, sp);

		for(int x = 1; x <= S; x++) {
			dp[x] = max(dp[x], sp[x]);
			for(int t = 1; t <= n; t++) {
				long long W = 1LL * w * t;
				long long P = 1LL * p * t;

				if(x >= W)
					dp[x] = max(dp[x], sp[x - W] + P);
			}
			dp[x] = max(dp[x], dp[x - 1]);
		}
	}

	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