Submission #1071821

#	Time	Username	Problem	Language	Result	Execution time	Memory
1071821		VectorLi	Knapsack (NOI18_knapsack)	C++14	73 / 100	1063 ms	18636 KiB

knapsack

#include <bits/stdc++.h>
#define long long long

using namespace std;

/*
优美二进制分组 
nklogk
*/

const int K = 2000;
const int MIN = numeric_limits<int>::min();

int n, k; 
long f[K + 1];
vector<pair<long, int>> a;

void split(int v, int w, int c) {
	assert(c > 0);
	for (int i = __lg(c) - 1; i >= 0; i--) {
		a.push_back({v * (1LL << i), w * (1 << i)});
	}
	c = c - (1 << __lg(c)) + 1;
	if (c > 0) {
		a.push_back({v * c, w * c});
	}
}

void solve() {
	cin >> k >> n;
	for (int i = 0; i < n; i++) {
		int v, w, c;
		cin >> v >> w >> c;
		c = min(c, k / w);
		split(v, w, c);
	}
	
	fill(f + 1, f + k + 1, MIN);
	for (auto [v, w] : a) {
		for (int i = k; i >= w; i--) {
			if (f[i - w] > MIN) {
				f[i] = max(f[i], f[i - w] + v);
			}
		}
	}
	cout << *max_element(f, f + k + 1) << "\n";
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int t;
	t = 1;
	for (int i = 0; i < t; i++) {
		solve();
	}
	return 0;
}

Compilation message (stderr)

knapsack.cpp: In function 'void solve()':
knapsack.cpp:39:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   39 |  for (auto [v, w] : a) {
      |            ^

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