Untitled

 avatar
unknown
plain_text
a year ago
1.2 kB
8
Indexable
#include <bits/stdc++.h>

using namespace std;


vector<long long> nums;
int n, k, x;

void insert(deque<long long>& dq, long long num) {
    while(dq.size() and num > dq.front()) {
        dq.pop_front();
    }
    dq.push_front(num);
}

void erase(deque<long long>& dq, long long num) {
    if (dq.size() and dq.back() == num) {
        dq.pop_back();
    }
}

void solve() {
    cin >> n >> k >> x;
    nums.resize(n);
    for(int i = 0; i < n; i++) {
        cin >> nums[i];
    }

    long long ans = -1e18;

    long long dp[5050][5050];

    deque<long long> dq;

    for (int idx = 0; idx < n; idx++) {
        if (idx + k >= n) dp[1][idx] = nums[idx];
        else dp[1][idx] = -1e18;
    }

    for(int rem = 2; rem <= x; rem++) {
        for(int idx = n - 1; idx >= 0; idx--) {
            if(idx + 1 < n) insert(dq, dp[rem-1][idx+1]);
            if(idx + k + 1 < n) erase(dq, dp[rem-1][idx + 1 + k]);
            dp[rem][idx] = nums[idx] + (dq.size() ? dq.back(): -1e18);
        }

    }

    for(int i = 0; i < k; i++) {
        ans = max(ans, dp[x][i]);
    }

    ans = ans < 0 ? -1 : ans;
    cout << ans;
}

int main() {
    int _t = 1;
    while(_t--) {
        solve();
        cout << "\n";
    }
}
Editor is loading...
Leave a Comment