Submission #2425373

---

Source Code Expand

#include <algorithm>
#include <cstring>
#include <deque>
#include <functional>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <vector>
using namespace std;
using ll = long long;

int main() {
  int M, N, K;
  while (cin >> N >> M >> K) {
    vector<ll> A(N);
    for (int i = 0; i < N; i++) cin >> A[i];
    vector<ll> dp = A;
    for (int i = 2; i <= K; i++) {
      vector<ll> ndp(N);
      deque<int> deq = {i - 2};
      for (int j = i - 1; j < N; j++) {
        while (deq.front() < j - M) {
          deq.pop_front();
        }
        ndp[j] = i * A[j] + dp[deq.front()];
        while (!deq.empty() && dp[deq.back()] <= dp[j]) {
          deq.pop_back();
        }
        deq.push_back(j);
      }
      dp = ndp;
    }
    ll res = *max_element(dp.begin(), dp.end());
    cout << res << endl;
  }
  return 0;
}

Submission Info

Judge Result