Submission #2999170

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a) for(int i=0;i<(a);i++)
const ll MOD=1000000007;

const int MAX_N=101010;

int n;
ll dat[2*MAX_N-1];
const ll INF=LLONG_MAX/2;

void init(int n_){
  n=1;
  while(n<n_) n*=2;
  for(int i=0;i<2*n-1;i++) dat[i]=-INF;
}

// ｋ番目の値をaに変更
void update(int k, ll a){
  k+=n-1;
  dat[k]=a;
  while(k>0){
    k=(k-1)/2;
    dat[k]=max(dat[k*2+1],dat[k*2+2]);
  }
}

//    ↓ a以上b未満の区間に注意
//[a,b)の最小値を求める
//外からはquery(a,b,0,0,n)とする
ll query(int a, int b, int k, int l, int r){
  if(r<=a || b<=l) return -INF;
  if(a<=l && r<=b) return dat[k];
  else{
    ll vl=query(a,b,k*2+1,l,(l+r)/2);
    ll vr=query(a,b,k*2+2,(l+r)/2,r);
    return max(vl,vr);
  }
}

ll A[101010];
ll dp[333][101010];

int main(){
  int N,M,K; cin>>N>>M>>K;
  rep(i,N) cin>>A[i+1];
  init(N+10);
  ll ans=0;
  for(int i=1;i<=K;i++){
    for(int j=1;j<=N;j++){
      int ind=max(0,j-M);
      dp[i][j]=A[j]*i+max(0LL,query(ind,j,0,0,N+1));
      ans=max(ans,dp[i][j]);
    }
    for(int j=1;j<=N;j++) update(j,dp[i][j]);
  }
  cout<<ans<<endl;
  return 0;
}

Submission Info

Judge Result