제출 #999091

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
999091		ef10	Knapsack (NOI18_knapsack)	C++17	73 / 100	1078 ms	2768 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];
	for (LL i = 0; i < 2; i++) {
		dp[i][0] = 0;
		for (LL j = 1; j < S+1; j++) {
			dp[i][j] = -1;
		}
	}
	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];
			if (dp[ind][j] < 0) continue;
			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