Submission #1012322

---

Source Code Expand

#include <iostream>
#include <deque>
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) {
    deque<int> deq;
    FOR(n, 1, N+1) {
      while(!deq.empty() && d[deq.back()][k-1] <= d[n-1][k-1])
        deq.pop_back();
      deq.push_back(n-1);
      while(deq.front() < n-M)
        deq.pop_front();
      d[n][k] = k * A[n] + d[deq.front()][k-1];
    }
  }

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

}

Submission Info

Judge Result