Submission #1167185

#	Time	Username	Problem	Language	Result	Execution time	Memory
1167185		guanglong	Knapsack (NOI18_knapsack)	C++20	73 / 100	1097 ms	16796 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<pair<long long, long long>> object;
	for (long long i = 1, v, w, k; i <= n; i++) {
		cin >> v >> w >> k;
		for (int j = 1; j <= k; k -= j, j *= 2) {
			if (w * j > 2000) goto next;			// 因为背包容量最大是 S，超过它的重量完全没有作用，避免 dp 时使用无效循环
			object.push_back({v * j, w * j});
		}
		if (k) object.push_back({v * k, w * k});
		next:;
	}
	
	vector<long long> dp(s + 1);
	for (auto it : object) {
		auto [v, w] = it;
		for (int j = s; j >= w; j--) {
			dp[j] = max(dp[j], dp[j - w] + v);
		}
	}
	
	cout << dp[s];
	return 0;
}

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