Submission #998060

---

Source Code Expand

#include <algorithm>
#include <iostream>
#include <queue>
using namespace std;

const int N = (int) 1e5;
long long f[N], g[N + 1];
int a[N];

int main() {
    ios::sync_with_stdio(false);
    int n, m, k; cin >> n >> m >> k;
    for (int i = 0; i < n; ++i) cin >> a[i];
    for (int t = k; t >= 1; --t) {
        for (int i = 0; i < n; ++i) g[i] = f[i];
        deque<int> q;
        q.push_back(n);
        if (t != k) g[n] = -1e18;
        for (int i = n - 1; i >= 0; --i) {
            while (!q.empty() && q.front() - i > m) q.pop_front();
            f[i] = g[q.front()] + 1LL * t * a[i];
            while (!q.empty() && g[i] >= g[q.back()]) q.pop_back();
            q.push_back(i);
        }
    }
    cout << *max_element(f, f + n) << endl;
    return 0;
}

Submission Info

Judge Result