Submission #998065

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int, ll> PII;

#define fi first
#define se second
#define mp make_pair
#define pb push_back

#define N 100010
#define K 310
int n, m, k;
ll a[N];

deque<PII> q[K];
ll S = 0;

void add(int x, PII y) {
	while (!q[x].empty() && q[x].back().se < y.se) q[x].pop_back();
	q[x].push_back(y);
}

void clr(int x, int nw) {
	while (!q[x].empty() && q[x].front().fi < nw - m) q[x].pop_front();
}

ll ans(int x) {
	if (q[x].empty()) return -1;
	return q[x].front().se;
}

int main () {
	cin >> n >> m >> k;
	for (int i = 0; i < n; i ++) cin >> a[i];
	for (int i = 0; i < n; i ++) {
		for (int j = k-1; j >= 1; j --) {
			clr(j, i);
			ll s = ans(j);
			if (s != -1) {
				add(j+1, mp(i, s+(ll)(j+1)*a[i]));
			}
		}
		add(1, mp(i, a[i]));
		S = max(S, ans(k));
	}
	
	cout << S << endl;
	return 0;
}

Submission Info

Judge Result