Submission #2121473

---

Source Code Expand

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#define lol(i,n) for(int i=0;i<n;i++)
#define mod 1000000007
typedef long long ll;
using namespace std;
#define N 100010
ll dp[310][N],a[N],n,m,k;
deque<pair<ll,ll> >Q;
int main(){
    cin>>n>>m>>k;
    lol(i,n)cin>>a[i];
    lol(i,k+1)lol(j,n+1)dp[i][j]=-1;
    lol(i,n)dp[1][i+1]=a[i];
    for(ll i=2;i<=k;i++){
	while(!Q.empty())Q.pop_front();
	for(ll j=0;j<=n;j++){
	    if(!Q.empty()&&Q.front().first!=-1){
		dp[i][j]=a[j-1]*i+Q.front().first;
	    }
	    while(!Q.empty()){
		if(Q.back().first<=dp[i-1][j]){
		    Q.pop_back();
		}
		else break;
	    }
	    Q.push_back(make_pair(dp[i-1][j],j));
	    while(!Q.empty()){
		if(Q.front().second<=j-m)Q.pop_front();
		else break;
	    }
	}
    }
    ll ans=0;
    lol(i,n+1)ans=max(ans,dp[k][i]);
    cout<<ans<<endl;
    return 0;
}

Submission Info

Judge Result