Submission #1054135

---

Source Code Expand

#ifndef ___Class_RMQ
#define ___Class_RMQ

// ------ Includes ------ //
#include <limits>
#include <vector>
#include <algorithm>

// ------ RMQ Class ------ //
template<typename Type> class RMQ {
private:
	unsigned size_; std::vector<Type> dat;
	inline Type query_(int a, int b, int k, int l, int r) {
		if (r <= a || b <= l) return std::numeric_limits<Type>::max();
		if (a <= l && r <= b) return dat[k];
		Type lc = query_(a, b, (k << 1), l, (l + r) >> 1);
		Type rc = query_(a, b, (k << 1) + 1, (l + r) >> 1, r);
		return std::min(lc, rc);
	}
public:
	RMQ() : size_(0), dat(std::vector<Type>()) {};
	RMQ(int size__) {
		for (size_ = 1; size_ < size__; ) size_ <<= 1;
		dat.resize(size_ << 1, std::numeric_limits<Type>::max());
	}
	template<class T>
	RMQ(T begin_, T end_) {
		int n = end_ - begin_;
		for (size_ = 1; size_ < n; size_ <<= 1); dat.resize(size_ << 1, std::numeric_limits<Type>::max());
		for (int i = 0; i < n; i++) dat[i + size_] = *(begin_ + i);
		for (int i = size_ - 1; i > 0; i--) dat[i] = std::min(dat[i << 1], dat[(i << 1) + 1]);
	}
	inline unsigned size() { return size_; }
	inline void update(int i, Type x) {
		i += size_; dat[i] = x;
		while (i > 1) {
			i >>= 1;
			dat[i] = std::min(dat[i << 1], dat[(i << 1) + 1]);
		}
	}
	inline Type query(int l, int r) {
		return query_(l, r, 1, 0, size_);
	}
};

#endif

#include <iostream>
using namespace std;
long long n, k, m, a[105000], dp[105000][325];
int main() {
	cin >> n >> m >> k; for (int i = 0; i < n; i++)cin >> a[i];
	vector<RMQ<long long>> x(k + 1, RMQ<long long>(n + 1));
	for (int i = 0; i <= n; i++) { for (int j = 0; j <= k; j++)dp[i][j] = -1LL << 62; }
	for (int i = 1; i <= n; i++) { dp[i][0] = 0; x[0].update(i, 0); }
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= k; j++) {
			dp[i][j] = (-1LL * x[j - 1].query(max(0LL, i - m), i)) + 1LL * j*a[i - 1];
			x[j].update(i, -dp[i][j]);
		}
	}
	long long maxn = 0; for (int i = 1; i <= n; i++)maxn = max(maxn, dp[i][k]);
	cout << maxn << endl;
	return 0;
}

Submission Info

Judge Result