제출 #1167215

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1167215		guanglong	Knapsack (NOI18_knapsack)	C++20	100 / 100	25 ms	1608 KiB

knapsack

#include <bits/stdc++.h>
#ifdef LOCAL
	#include <windows.h>
#endif
using namespace std;

#ifdef LOCAL
	template<typename T>
	void debugPrint(int line, const string& varName, const T& value) {
		SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), 10);
	    cerr << "Line " << line << ": " << varName << " = " << value << "\n";
	    SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), 7);
	}
	
	#define dbg(x) debugPrint(__LINE__, #x, x)
#endif

#define TestCases int TC; cin >> TC; while (TC--)

template <class Fun> class y_combinator_result {
	Fun fun_;
public:
	template <class T>
	explicit y_combinator_result(T &&fun) : fun_(std::forward<T>(fun)) {}

	template <class... Args> decltype(auto) operator()(Args &&...args) {
		return fun_(std::ref(*this), std::forward<Args>(args)...);
	}
};

template <class Fun> decltype(auto) y_combinator(Fun &&fun) {
	return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));
}

struct AUTOIOS {
	AUTOIOS() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); }
} autoios;

constexpr int modulo = 1e9 + 7;
mt19937 mt(static_cast<unsigned>(time(nullptr)));
uniform_int_distribution<int> range(0, 2);

template<typename T>
struct CMP {
	bool operator() (const T &a, const T &b) const {
		return a < b;
	}
};

int main() {
	int s, n;
	cin >> s >> n;
	
	vector<vector<pair<int, int>>> weight(s + 1);
	for (int i = 1, v, w, k; i <= n; i++) {
		cin >> v >> w >> k;
		
		if (w > s) continue;
		weight[w].push_back({v, k});
	}
	
	vector<int> dp(s + 1);
	for (int w = 1; w <= s; w++) {
		sort(weight[w].begin(), weight[w].end(), greater<pair<int, int>>());
		
		// 挑选 weight = w 重量时，前 s / w 个 value 最高的物品
		int num = s / w;
		for (auto it : weight[w]) {
			// 对于 weight = w 物品时，至多选择 take 个物品(二进制优化法)
			auto [v, k] = it; int take = min(k, num); num -= take;
			for (int b = 1, bv, bw; b <= take; take -= b, b *= 2) {
				bv = b * v;
				bw = b * w;
				
				if (bw > s) break;
				for (int i = s; i >= bw; i--) {
					dp[i] = max(dp[i], dp[i - bw] + bv);
				}
			}
			if (take && take * w <= s) for (int i = s; i >= take * w; i--) {
				dp[i] = max(dp[i], dp[i - take * w] + take * v);
			}
			
			if (num == 0) break;
		}
	}
	
	cout << dp[s];
	return 0;
}

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