Submission #2066659

---

Source Code Expand

#include <iostream>
#define llint long long

using namespace std;

llint seg[305][1<<18];

void init(llint seg[])
{
	for(int i = 0; i < (1<<18); i++) seg[i] = 0;
}

void update(llint seg[], int i, llint val)
{
	i += (1 << 17);
	seg[i] = val;
	while(i > 1){
		i /= 2;
		seg[i] = max(seg[i*2], seg[i*2+1]);
	}
}

llint query(llint seg[], int a, int b, int k, int l, int r)
{
	if(b < l || r < a) return 0;
	if(a <= l && r <= b) return seg[k];
	llint lval = query(seg, a, b, k*2, l, (l+r)/2);
	llint rval = query(seg, a, b, k*2+1, (l+r)/2+1, r);
	return max(lval, rval);
}

llint M, N, K;
llint A[100005];

int main(void)
{
	cin >> N >> M >> K;
	for(int i = 1; i <= N; i++) cin >> A[i];
	
	for(int i = 1; i <= N; i++){
		for(int j = 1; j <= K; j++){
			llint val = query(seg[j-1],  max(0LL, i-M), i-1, 1, 0, (1<<17)-1 ) + j * A[i];
			update(seg[j], i, val);
		}
	}
	
	cout << query(seg[K], 0, N, 1, 0, (1<<17)-1 ) << endl;
	return 0;
}

Submission Info

Judge Result