Submission #2121441

---

Source Code Expand

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<set>
#include<map>
#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;
map<ll,ll> mp;
void Push(ll x){
    if(x==-1)return;
    mp[x]++;
}
void Erase(ll x){
    if(x==-1)return;
    mp[x]--;
    if(mp[x]==0)mp.erase(x);
}
ll Top(){
    if(mp.size()==0)return -(ll)mod*(ll)mod;
    map<ll,ll>::iterator it=mp.end();it--;
    return it->first;
}
int main(){
    cin>>n>>m>>k;
    lol(i,n)cin>>a[i+1];
    lol(i,k+1)lol(j,n+1)dp[i][j]=-1;
    dp[0][0]=0;
    for(int i=1;i<=k;i++){
	mp.clear();
	for(int j=0;j<=n;j++){
	    if(j>=i)dp[i][j]=a[j]*i+Top();
	    Push(dp[i-1][j]);
	    if(j-m-1>=0){
		Erase(dp[i-1][j-m-1]);
	    }
	}
    }
    ll ans=0;
    lol(i,n+1)ans=max(ans,dp[k][i]);
    cout<<ans<<endl;
    return 0;
}

Submission Info

Judge Result