Submission #3216890

---

Source Code Expand

#include <bits/stdc++.h>
typedef long long i64;
using std::cout;
using std::endl;
using std::cin;

struct SegmentTree {
	std::vector<i64> seg;
	int sz = 1;
	
	SegmentTree(int n) {
		while(sz < n) sz *= 2;
		seg.assign(sz * 2 - 1, 0);
	}
	
	void update(int k, i64 x) {
		k += sz - 1;
		seg[k] = x;
		
		while(k) {
			k = (k - 1) / 2;
			
			seg[k] = std::max(seg[2 * k + 1], seg[2 * k + 2]);
		}
	}
	
	i64 get(int a, int b, int k, int l, int r) {
		if(r<=a||b<=l) return 0;
		if(a<=l&&r<=b) return seg[k];
		
		return std::max(get(a, b, 2 * k + 1, l, (l + r) / 2), get(a, b, 2 * k + 2, (l + r) / 2, r));
	}
	
	i64 get(int a, int b) {
		return get(a, b, 0, 0, sz);
	}
};

int main(){
	int n, m, k; cin >> n >> m >> k; std::vector<i64> a(n);
	for(int i = 0; i < n; i++) cin >> a[i];
	
	SegmentTree dp[k + 1](n + 1);
	for(int i = 0; i < n; i++) dp[0].update(i, 1);
	for(int i = 0; i < n; i++) {
		for(i64 j = 0; j < k; j++) {
			i64 tmp = dp[j].get(std::max(0, i - m), i + 1);
			if(!tmp) continue;
			
			dp[j + 1].update(i + 1, tmp + a[i] * (j + 1LL));
		}
	}
	
	cout << dp[k].get(0, n + 1) - 1 << endl;
	return 0;
}

Submission Info

Judge Result