Submission #2425226

---

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++) {
      multiset<ll> S;
      for (int j = 0; j < N; j++) {
        ll best = i * A[j];
        if (S.size() > 0) {
          auto it = S.end();
          --it;
          best += *it;
        }
        S.insert(dp[j]);
        if (S.size() > M) {
          S.erase(S.begin());
        }
        dp[j] = best;
      }
    }
    ll res = *max_element(dp.begin(), dp.end());
    cout << res << endl;
  }
  return 0;
}

Submission Info

Judge Result