Submission #1913619

---

Source Code Expand

#include <iostream>
#include <deque>
#include <vector>
#include <algorithm>
using namespace std;

class Slide_Max {
public:
	vector<long long>dat; long long size_, L = 0, R = -1;
	deque<pair<long long, long long>>Q;

	void init(int size__) {
		size_ = size__;
		dat.resize(size_, 0);
	}
	void update(long long p, long long x) {
		dat[p] = x;
	}
	long long query(long long l, long long r) {
		while (R < r) {
			R++;
			while (!Q.empty()) {
				pair<long long, long long>A = Q.back();
				if (A.first <= dat[R])Q.pop_back();
				else break;
			}
			Q.push_back(make_pair(dat[R], R));
		}
		while (L < l) {
			while (!Q.empty()) {
				pair<long long, long long>A = Q.front();
				if (A.second == L)Q.pop_front();
				else break;
			}
			L++;
		}
		return Q.front().first;
	}
};

long long N, M, K, a[100009], dp[309][100009];

int main() {
	cin >> N >> M >> K;
	for (int i = 1; i <= N; i++)cin >> a[i];
	for (int i = 0; i < 309; i++) { for (int j = 0; j < 100009; j++)dp[i][j] = (-1LL << 62); }
	dp[0][0] = 0;
	for (int i = 0; i < K; i++) {
		Slide_Max X; X.init(N + 3);
		for (int j = 0; j <= N; j++) X.update(j, dp[i][j]);
		for (int j = 1; j <= N; j++) {
			long long L = j - M, R = j - 1; if (L < 0)L = 0;
			dp[i + 1][j] = 1LL * (i + 1)*a[j] + X.query(L, R);
		}
	}
	long long maxn = 0;
	for (int i = 0; i <= N; i++)maxn = max(maxn, dp[K][i]);
	cout << maxn << endl;
	return 0;
}

Submission Info

Judge Result