CF1077F2 Pictures with Kittens (hard version)

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.

N/A

N/A