Submission #8658157

---

Source Code Expand

/**
 *    author:  tourist
 *    created: 26.11.2019 09:39:34       
**/
#include <bits/stdc++.h>

using namespace std;

template <typename T, class F = function<T(const T&, const T&)>>
class SparseTable {
 public:
  int n;
  vector<vector<T>> mat;
  F func;

  SparseTable(const vector<T>& a, const F& f) : func(f) {
    n = static_cast<int>(a.size());
    int max_log = 32 - __builtin_clz(n);
    mat.resize(max_log);
    mat[0] = a;
    for (int j = 1; j < max_log; j++) {
      mat[j].resize(n - (1 << j) + 1);
      for (int i = 0; i <= n - (1 << j); i++) {
        mat[j][i] = func(mat[j - 1][i], mat[j - 1][i + (1 << (j - 1))]);
      }
    }
  }

  T get(int from, int to) const {
    assert(0 <= from && from <= to && to <= n - 1);
    int lg = 32 - __builtin_clz(to - from + 1) - 1;
    return func(mat[lg][from], mat[lg][to - (1 << lg) + 1]);
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, m, k;
  cin >> n >> m >> k;
  vector<int> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  vector<long long> dp(n);
  for (int i = 0; i < n; i++) {
    dp[i] = a[i];
  }
  for (int it = 1; it < k; it++) {
    vector<long long> new_dp(n);
    new_dp[0] = (long long) -1e18;
    SparseTable<long long> st(dp, [&](long long i, long long j) { return max(i, j); });
    for (int i = 1; i < n; i++) {
      new_dp[i] = st.get(max(i - m, 0), i - 1) + (it + 1LL) * a[i];
    }
    swap(dp, new_dp);
  }
  cout << *max_element(dp.begin(), dp.end()) << '\n';
  return 0;
}

Submission Info

Judge Result