Submission #999074

#	Time	Username	Problem	Language	Result	Execution time	Memory
999074		ef10	Knapsack (NOI18_knapsack)	C++17	73 / 100	1033 ms	3900 KiB

knapsack

// Source: https://usaco.guide/general/io

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

#define LL long long

int main() {
	LL S, N; cin >> S >> N;
	LL V[N+1]; memset(V,0,sizeof(V));
	LL W[N+1]; memset(W,0,sizeof(W));
	LL K[N+1]; memset(K,0,sizeof(K));
	for (LL i = 1; i <= N; i++) {
		cin >> V[i] >> W[i] >> K[i];
	}
	LL dp[2][S+1]; memset(dp,0,sizeof(dp));
	for (LL i = 1; i <= N; i++) {
		LL ind = i%2;
		LL oi = (i+1)%2;
		for (LL j = S; j >= 0; j--) {
			dp[ind][j] = dp[oi][j];
			for (LL w = W[i],c=1; w+j <= S && c<=K[i]; w+=W[i],c++) {
				dp[ind][w+j] = max(dp[ind][w+j], dp[ind][j]+V[i]*c);
			}
		}
	}
	LL res = 0;
	for (LL i = 1; i <= S; i++) {
		res = max(res, dp[N%2][i]);
	}
	cout << res << endl;
}

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