Submission #1053961

#	Time	Username	Problem	Language	Result	Execution time	Memory
1053961		ssitaram	Knapsack (NOI18_knapsack)	C++17	12 / 100	1 ms	348 KiB

knapsack

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

typedef long long ll;

struct item {
	ll v, w, k;
};

int main() {
	ios::sync_with_stdio(0);
	cin.tie(nullptr);
	ll s, n; cin >> s >> n;
	vector<item> v(n);
	for (ll i = 0; i < n; ++i) {
		cin >> v[i].v >> v[i].w >> v[i].k;
	}
	vector<ll> best(s + 1);
	for (ll i = 0; i < n; ++i) {
		ll fr = 0;
		ll bfr = best[fr];
		for (ll j = 0; j <= s; ++j) {
			ll o = bfr + v[i].v * min((j - fr) / v[i].w, v[i].k);
			if (best[j] > o || (best[j] == o && j - fr % 4 == 0)) {
				fr = j;
				bfr = best[fr];
			}
			if (j != 0) best[j] = max(best[j], best[j - 1]);
			best[j] = max(best[j], bfr + v[i].v * min((j - fr) / v[i].w, v[i].k));
		}
	}
	cout << *max_element(best.begin(), best.end()) << '\n';
	return 0;
}

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