Untitled
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