Submission #1012300

---

Source Code Expand

#include <iostream>
#include <set>
using namespace std;

#define int long long
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)

const int INF = 1 << 30;

int A[100005];
int d[100005][305];

signed main() {
  ios::sync_with_stdio(false);

  int N, M, K;
  cin >> N >> M >> K;

  REP(n, N)
    cin >> A[n+1];

  REP(n, N)
    REP(k, K)
      d[n][k] = -INF;

  d[0][0] = 0;
  FOR(n, 1, N+1)
    d[n][1] = A[n];


  FOR(k, 2, K+1) {
    multiset<int> st;
    FOR(n, 1, N+1) {
      st.insert(d[n-1][k-1]);
      if(n-M-1 >= 0)
        st.erase(d[n-M-1][k-1]);
      d[n][k] = k * A[n] + (*st.rbegin());
    }
  }

  int result = -INF;
  REP(n, N+1)
    result = max(result, d[n][K]);
  cout << result << endl;

}

Submission Info

Judge Result