Submission #400939

#	Time	Username	Problem	Language	Result	Execution time	Memory
400939		benk	Knapsack (NOI18_knapsack)	C++14	73 / 100	1086 ms	10104 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++) {
		int val = 1;
		int cnt = 1;
		while (2 * val + 1 <= k[i]) {
			val = 2 * val + 1;
			v.pb(v[i] * (1 << cnt));
			w.pb(w[i] * (1 << cnt));
			cnt++;
		}
		int rem = k[i] - val;
		v.pb(v[i] * rem);
		w.pb(w[i] * rem);
	}

	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