Pictures with Kittens (hard version)
Contest: Codeforces Round 521 (Div. 3)
Difficulty rating: 2100
Tags: data structures, dp

The only difference between easy and hard versions is the constraints.

Vova likes pictures with kittens. The news feed in the social network he uses can be represented as an array of $$$n$$$ consecutive pictures (with kittens, of course). Vova likes all these pictures, but some are more beautiful than the others: the $$$i$$$-th picture has beauty $$$a_i$$$.

Vova wants to repost exactly $$$x$$$ pictures in such a way that:

- each segment of the news feed of at least $$$k$$$ consecutive pictures has at least one picture reposted by Vova;
- the sum of beauty values of reposted pictures is maximum possible.

For example, if $$$k=1$$$ then Vova has to repost all the pictures in the news feed. If $$$k=2$$$ then Vova can skip some pictures, but between every pair of consecutive pictures Vova has to repost at least one of them.

Your task is to calculate the maximum possible sum of values of reposted pictures if Vova follows conditions described above, or say that there is no way to satisfy all conditions.

Input format:
The first line of the input contains three integers $$$n, k$$$ and $$$x$$$ ($$$1 \le k, x \le n \le 5000$$$) — the number of pictures in the news feed, the minimum length of segment with at least one repost in it and the number of pictures Vova is ready to repost.

The second line of the input contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$), where $$$a_i$$$ is the beauty of the $$$i$$$-th picture.

Output format:
Print -1 if there is no way to repost some pictures to satisfy all the conditions in the problem statement.

Otherwise print one integer — the maximum sum of values of reposted pictures if Vova follows conditions described in the problem statement.

Constraints:
Time limit: 2.5 s
Memory limit: 512.0 MB

Example input:
5 2 3
5 1 3 10 1

Example output:
18

Example input:
6 1 5
10 30 30 70 10 10

Example output:
-1

Editorial:
Let's use dynamic programming described in the previous tutorial to solve this problem too. But its complexity is $$$O(nkx)$$$ so we have to improve some part of the solution.
Let's see how we do transitions in this dp: for $$$p \in [i-k; i-1]$$$ $$$dp_{i, j} = max(dp_{i, j}, dp_{p, j + 1} + a_i)$$$. What can we do to optimize it? $$$a_i$$$ is the constant and we have to take the maximum value among $$$dp_{i - k, j + 1}, dp_{i - k + 1, j + 1}, \dots, dp_{i - 1, j + 1}$$$. You will say "segment tree"! I say no. Not a segment tree. Not a sparse table. Not a cartesian tree or some other logarithmic data structures. If you want to spend a lot of time to fit such solution in time and memory limits — okay, it is your choice. I prefer the queue with supporting the maximum on it.
The last part of this tutorial will be a small guide about how to write and use the queue with supporting the maximum on it.
The first part of understanding this data structure is the stack with the maximum. How do we support the stack with the maximum on it? That's pretty easy: let's maintain the stack of pairs, when the first value of pair is the value in the stack and the second one is the maximum on the stack if this element will be the topmost. Then when we push some value $$$val$$$ in it, the first element of pair will be $$$val$$$ and the second one will be $$$max(val, s.top().second)$$$ (if $$$s$$$ is our stack and $$$top()$$$ is the topmost element). When we pop the element we don't need any special hacks to do it. Just pop it. And the maximum on the stack is always $$$s.top().second$$$.
Okay, the second part of understanding this data structure is the queue on two stacks. Let's maintain two stacks $$$s1$$$ and $$$s2$$$ and try to implement the queue using it. We will push elements only to $$$s2$$$ and pop elements only from $$$s1$$$. Then how to maintain the queue using such stacks? The push is pretty easy — just push it in $$$s2$$$. The main problem is pop. If $$$s1$$$ is not empty then we have to pop it from $$$s1$$$. But what do we do if $$$s1$$$ is empty? No problems: let's just transfer elements of $$$s2$$$ to $$$s1$$$ (pop from $$$s2$$$, push to $$$s1$$$) in order from top to bottom. And don't forget to pop the element after this transfer!
Okay, if we will join these two data structures, we can see that we obtain exactly what we want! Just two stacks with maximums! That's pretty easy to understand and implement it.
The last part of the initial solution is pretty easy — just apply this data structure (in fact, $$$x+1$$$ data structures) to do transitions in our dynamic programming. The implementation of this structure can be found in the authors solution.
Total complexity of the solution is $$$O(nx)$$$.