Submission #758539

#	Time	Username	Problem	Language	Result	Execution time	Memory
758539		IBory	Knapsack (NOI18_knapsack)	C++14	100 / 100	242 ms	12904 KiB

knapsack

#include <bits/stdc++.h>
#define pii pair<ll, ll>
typedef long long ll;
using namespace std;

const int MAX = 2004;
vector<ll> cand[MAX];
ll dp[2][MAX];

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	ll N, S;
	cin >> S >> N;
	for (int i = 0; i < N; ++i) {
		ll a, b, c, n = 1;
		cin >> a >> b >> c;
		vector<ll> V;
		V.push_back(1);
		c--;
		while (c) {
			if (n > c) n = c;
			V.push_back(n);
			c -= n;
			n <<= 1LL;
		}
		for (ll n : V) {
			if (b * n >= MAX) break;
			cand[b * n].push_back(a * n);
		}
	}

	vector<pii> P;
	for (int i = 1; i < MAX; ++i) {
		sort(cand[i].begin(), cand[i].end(), greater<ll>());
		for (int n = 0; n < min(MAX / i, (int)cand[i].size()); ++n) P.emplace_back(i, cand[i][n]);
	}

	N = P.size();
	memset(dp, 0xff, sizeof(dp));
	dp[1][0] = 0;
	for (int i = 0; i < N; ++i) {
		swap(dp[0], dp[1]);
		memset(dp[1], 0xff, sizeof(dp[1]));
		for (int n = 0; n <= S; ++n) {
			if (dp[0][n] == -1) continue;
			dp[1][n] = max(dp[1][n], dp[0][n]);
			if (n + P[i].first <= S) dp[1][n + P[i].first] = max(dp[1][n + P[i].first], dp[0][n] + P[i].second);
		}
	}

	ll ans = 0;
	for (int n = 0; n <= S; ++n) ans = max(ans, dp[1][n]);
	cout << ans;
	return 0;
}

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