제출 #1071813

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1071813		VectorLi	Knapsack (NOI18_knapsack)	C++17	17 / 100	1 ms	348 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) {
	for (int i = __lg(c); i >= 0; i--) {
		a.push_back({v * (1LL << i), w * (1 << i)});
		c = c - (1 << i);
	}
	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;
}

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