Submission #1262851

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262851		khanghb2006	Knapsack (NOI18_knapsack)	C++20	73 / 100	1091 ms	5536 KiB

knapsack

#include<bits/stdc++.h>
using namespace std;
#define TASK "task"

const int mxN = 5e5 + 7;
const int inf = 1e9 + 67;

struct item {
	int w , v , k;
}a[mxN];

int n;
int S;
long long dp[mxN];

void solve(void) {
	cin >> S >> n;
	for (int i = 1; i <= n; i++) 
		cin >> a[i].v >> a[i].w >> a[i].k;
	memset(dp , -0x3f , sizeof dp);
	dp[0] = 0;
	for (int i = 1; i <= n; i++) {
		if(!a[i].w) {
			for (int j = 0; j <= S; j++)
				dp[j] += 1LL * a[i].v * a[i].k;
			continue;
		}
		int c = 1;
		while(a[i].k > 0) {
			int can = min(c , a[i].k);
			long long W = 1LL * can * a[i].w;
			long long V = 1LL * can * a[i].v;
			for (long long j = S; j >= W; j--)
				dp[j] = max(dp[j] , dp[j - W] + V);
			a[i].k -= can;
			c *= 2;
		}
	}
	long long ans = -inf;
	for (int i = 0; i <= S; i++)
		ans = max(ans , dp[i]);
	cout << ans;	
}

int main() {
	ios_base :: sync_with_stdio(0);
	cin.tie(0);
	//freopen(TASK".inp","r",stdin);
	//freopen(TASK".out","w",stdout);
	int tc = 1;
	//cin >> tc;
	while(tc--) solve();
	return 0;
}

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