Submission #630629

#	Time	Username	Problem	Language	Result	Execution time	Memory
630629		dutinmeow	Knapsack (NOI18_knapsack)	C++17	73 / 100	1092 ms	1492 KiB

knapsack

#include <bits/stdc++.h>

template<typename T>
struct lazy_monotonic_stack {
	std::stack<std::tuple<T, T, T>> stk;

public:
	void push(T x) { stk.emplace(x, stk.empty() ? x : std::max(query(), x), 0); }

	void update(T x) { if (!stk.empty()) std::get<2>(stk.top()) += x; }

	T top() { return std::get<0>(stk.top()) + std::get<2>(stk.top()); }

	T query() { return stk.empty() ? std::numeric_limits<T>::min() : std::get<1>(stk.top()) + std::get<2>(stk.top()); }

	void pop() { T x = std::get<2>(stk.top()); stk.pop(), update(x); }

	int size() { return stk.size(); }

	bool empty() { return stk.empty(); }
};

template<typename T>
struct lazy_monotonic_queue {
	lazy_monotonic_stack<T> stk1, stk2;

	void shift() { 
		if (!stk2.empty())
			return;
		while (!stk1.empty()) {
			stk2.push(stk1.top());
			stk1.pop();
		}
	}

public:
	void push(T x) { stk1.push(x); }

	void update(T x) { stk1.update(x), stk2.update(x); }

	T query() { return std::max(stk1.query(), stk2.query()); }

	void pop() { shift(), stk2.pop(); }

	int size() { return stk1.size() + stk2.size(); }

	bool empty() { return stk1.empty() && stk2.empty(); }
};

int main() {
	using namespace std;
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int M, N;
	cin >> M >> N;
	vector<int> S(N), H(N), K(N);
	for (int i = 0; i < N; i++)
		cin >> S[i] >> H[i] >> K[i];

	vector<int> dp1(M + 1), dp2(M + 1);
	fill(dp1.begin(), dp1.end(), (int)-1e9);
	dp1[0] = 0;
	for (int i = 0; i < N; i++) {
		for (int s = 0; s < H[i]; s++) {
			lazy_monotonic_queue<int> lmq;
			for (int j = s; j <= M; j += H[i]) {
				if (lmq.size() > K[i])
					lmq.pop();
				lmq.push(dp1[j]);
				dp2[j] = lmq.query();
				lmq.update(S[i]);
			}
		}
		dp1 = dp2;
	}

	cout << *max_element(dp1.begin(), dp1.end()) << '\n';
}

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