Submission #3639467

---

Source Code Expand

#include <bits/stdc++.h>
#define ll long long
#define REP(i, n) for (ll i = 0, max_i = (n); i < max_i; i++)
#define REPI(i, a, b) for (ll i = (a), max_i = (b); i < max_i; i++)
#define ALL(obj) (obj).begin(), (obj).end()
#define RALL(obj) (obj).rbegin(), (obj).rend()
#define fi first
#define se second
#define pb push_back
#define debug(x) cerr << #x << ": " << (x) << endl
#define debug2(x, y) cerr << #x << ": " << (x) << " " << #y << ": " << y << endl;
#define int long long
using namespace std;
using II = pair<int, int>;
using VII = vector<II>;
using VI = vector<int>;
using VVI = vector<VI>;
using VVVI = vector<VVI>;
template <class T = int> inline T in() { T x; cin >> x; return x; }
template <class T = int> inline bool chmax(T &a, const T &b) { if (a < b) { a = b; return true; } return false; }
template <class T = int> inline bool chmin(T &a, const T &b) { if (a > b) { a = b; return true; } return false; }
template <class T> ostream& operator<<(ostream &s, const vector<T>& d) { int n = d.size(); REP (i, n) s << d[i] << " "; return s; }
template <class T> ostream& operator<<(ostream &s, const vector<vector<T>>& dd) { for (vector<T> d: dd) s << d << endl; return s; }
struct Fast { Fast() { cin.tie(0); ios::sync_with_stdio(false); } } fast;
const int MOD = 1e9 + 7;

template <class T = int>
vector<T> slide_min(const vector<T>& a, int w, function<bool(T, T)> cmp = less<T>()) {
  int n = a.size();
  vector<T> ret(n);
  deque<T> dq;
  REP (i, n) {
    while (!dq.empty() && !cmp(a[dq.back()], a[i])) {
      dq.pop_back();
    }
    dq.push_back(i);
    while (dq.front() <= i - w) {
      dq.pop_front();
    }
    ret[i] = dq.front();
  }
  return ret;
}

signed main() {
  int N, M, K; cin >> N >> M >> K;
  VI A(N);
  REP (i, N) cin >> A[i];

  VVI dp(K + 1, VI(N + 1, 0));
  REPI (i, 1, K + 1) {
    dp[i][0] = -1;
  }
  VVI mas(K + 1, VI(N + 1));
  REPI (i, 1, K + 1) {
    REPI (j, 1, N + 1) {
      dp[i][j] = dp[i - 1][mas[i - 1][j - 1]] + i * A[j - 1];
    }
    // スライド最大値
    mas[i] = slide_min<int>(dp[i], K, greater<int>());
  }
  int ans = 0;
  REP (j, N + 1) {
    ans = max(ans, dp[K][j]);
  }
  cout << ans << endl;
}

Submission Info

Judge Result