Submission #3275377

---

Source Code Expand

#include <iostream>
using namespace std;
typedef long long ll;

int N,M,K;
ll A[100010],dp[100010][310] = {{0}},D[100010] = {0};

int main(){
	cin >> N >> M >> K;
	for(int i=1;i<=N;i++){
		cin >> A[i];
		dp[i][1] = A[i];
	}
	int s = 0,t = 0;
	for(ll j=2;j<=K;j++){
		for(int i=1;i<N;i++){
			while(s<t && dp[D[t-1]][j-1]<=dp[i][j-1]) t--;
			D[t] = i;
			t++;
			if(j-1<=i){
				int m = D[s];
				dp[i+1][j] = dp[m][j-1] + j*A[i+1];
				if(i>=M && D[s]==i-M+1) s++;
			}
		}
		for(int i=0;i<=N;i++) D[i] = 0;
		s = 0; t = 0;
	}
	ll ans = 0;
/*	for(int j=1;j<=K;j++){
		for(int i=1;i<=N;i++){
			cout << dp[i][j] << (i!=N? " ":"\n");
		}
	}
*/	for(int i=K;i<=N;i++) ans = max(ans,dp[i][K]);
	cout << ans << endl;
}

Submission Info

Judge Result