Submission #400938

#	Time	Username	Problem	Language	Result	Execution time	Memory
400938		benk	Knapsack (NOI18_knapsack)	C++14	73 / 100	1088 ms	11408 KiB

knapsack

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

#define all(x)      x.begin(), x.end()
#define pb          push_back
#define sz(x)       (int)(x.size())
#define ll          long long
#define fi          first
#define se          second
#define lbd         lower_bound
#define ubd         upper_bound

const int MOD = 1e9 + 7;
const double eps = 1e-10;
const long long INF = 1e18;
const int N = 2e6 + 10;

ll dp[2005];
void solve() {
	int W, n;
	cin >> W >> n;
	vector<int> v(n), w(n), k(n);
	for (int i = 0; i < n; i++) {
		cin >> v[i] >> w[i] >> k[i];
		k[i] = min(k[i], W / w[i]);
	}

	for (int i = 0; i < n; i++) {
		if (k[i] == 0 || k[i] == 1) continue;
		int hi = log2(k[i]);
		if (pow(2, hi + 1) - 1 == k[i]) {
			for (int j = 1; j <= hi; j++) {
				v.pb(v[i] * (1 << j));
				w.pb(w[i] * (1 << j));
			}
		}
		else {
			for (int j = 1; j < hi; j++) {
				v.pb(v[i] * (1 << j));
				w.pb(w[i] * (1 << j));
			}
			int lft = k[i] - (1 << hi) + 1;
			v.pb(v[i] * lft);
			w.pb(w[i] * lft);
		}
	}

	n = sz(v);
	for (int i = 0; i < n; i++) {
		for (int j = W; j >= w[i]; j--) {
			dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
		}
	}

	ll ans = 0;
	for (int i = 0; i <= W; i++) {
		ans = max(ans, dp[i]);
	}
	cout << ans;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	int tt = 1;
	//cin >> tt;
	while (tt--) {
		solve();
	}
	return 0;
}

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