Submission #2067008

---

Source Code Expand

#include <iostream>
#include <deque>
#define llint long long
#define inf 1000000000000000000

using namespace std;

llint M, N, K;
llint A[100005];
llint dp[100005][305];
deque<llint> deq[305];

int main(void)
{
	cin >> N >> M >> K;
	for(int i = 1; i <= N; i++) cin >> A[i];
	
	for(int i = 0; i <= K; i++){
		dp[0][i] = -inf;
		deq[i].push_back(0);
	}
	dp[0][0] = 0;
	
	for(int i = 1; i <= N; i++){
		for(int j = 1; j <= K; j++){
			dp[i][j] = dp[deq[j-1].back()][j-1] + j * A[i];
		}
		for(int j = 1; j <= K; j++){
			if(deq[j].back() == i-M) deq[j].pop_back();
			while(deq[j].size() && dp[deq[j].front()][j] <= dp[i][j]) deq[j].pop_front();
			deq[j].push_front(i);
		}
	}
	
	llint ans = 0;
	for(int i = 0; i <= N; i++) ans = max(ans, dp[i][K]);
	
	cout << ans << endl;
	return 0;
}

Submission Info

Judge Result