Submission #1271856

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271856		wqq	Knapsack (NOI18_knapsack)	C++20	29 / 100	143 ms	1864 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
#define ent "\n"
#define all(a) (a).begin(), (a).end()
#define int int64_t
#define pii pair<int,int>
using ld = long double;
const int MOD = 1e9 + 7;
const int inf = 1e18;


int32_t main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
	int s, n;
	cin >> s >> n;
	vector<array<int, 3>> a(n);
	bool isk1 = 1;
	for (int i = 0; i < n; ++i) {
		cin >> a[i][0] >> a[i][1] >> a[i][2];
		if (a[i][2] != 1) {
			isk1 = 0;
		}
	}
	if (n == 1) {
		int ans = 0;
		for (int i = 1; i <= a[0][2]; ++i) {
			if (a[0][1] * i <= s) {
				ans = a[0][0] * i;
			}
		}
		cout << ans;
	}
	else if (isk1) {
		// dp[i][j] = i elements with j -> cost
		vector<vector<int>> dp(n+1,vector<int> (s+1,-inf));
		dp[0][0] = 0;
		for (int i = 0; i < n; ++i) {
			if (a[i][1] <= s) {
				dp[1][a[i][1]] = a[i][2];
			}
		}
		for (int i = 1; i <= n; ++i) {
			for (int j = 0; j <= s; ++j) {
				dp[i][j] = dp[i - 1][j];
				int prev = j - a[i - 1][1];
				if (prev >= 0 && dp[i - 1][prev] != -inf) {
					dp[i][j] = max(dp[i][j], dp[i - 1][prev] + a[i - 1][0]);
				}
			}
		}
		int ans = 0;
		for (int i = 1; i <= n; ++i) {
			for (int j = 0; j <= s; ++j) {
				ans = max(ans, dp[i][j]);
			}
		}
		cout << ans;
	}
}


 
int binpow(int base, int power) {
	if (power == 0) return 1;
	if (power == 1) return base;
	int x = binpow(base, power / 2);
	if (power & 1) return x * x * base;
	else return x * x;
}
 
int lcm(int a, int b) {
	return a / __gcd(a,b) * b;
}

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