Submission #998019

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;
typedef long long ll;
typedef vector<int> vi;

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define rep(i,n) rep2(i,0,n)
#define rep2(i,m,n) for(int i=m;i<(n);i++)
#define ALL(c) (c).begin(),(c).end()

ll dp[2][300010];

vector<int> slideMinimum(const vector<ll> &a, int k) {
    int n = a.size();
    deque<int> deq;
    vector<int> res;
    for (int i = 0; i < n; i++) {
        while (deq.size() && a[deq.back()] >= a[i]) deq.pop_back();
        deq.push_back(i);
        if (i - k + 1 >= 0) {
            res.push_back(deq.front());
            if (deq.front() == i - k + 1) deq.pop_front();
        }
    }
    return res;
}

int M, N, K;
ll A[100010];

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

	int c = 0, f = 1;

	memset(dp, -1, sizeof(dp));

	rep(i, N) dp[0][i+1] = A[i];

	rep(t, K-1) {
		for (int j = 0; j <= N; ++j) {
			dp[f][j] = -1;
		}

		deque<int> deq;
		
		for (int i = 0; i < N; i++) {
			if (dp[c][i] != -1) {
				while (deq.size() && dp[c][deq.back()] <= dp[c][i]) deq.pop_back();
				deq.push_back(i);
			}

			if (deq.size()) {
				dp[f][i+1] = dp[c][deq.front()] + (ll)(t + 2) * A[i];
				if (deq.front() == i - M) deq.pop_front();
			}
		}

		swap(c, f);
	}

	cout << *max_element(dp[c], dp[c] + N + 1) << endl;

	return 0;
}

Submission Info

Judge Result