Prizes
Time limit1sMemory limit1024 MB
Given n prize values and a block length k, Alice picks one block of k consecutive prizes first; find the minimum value Bob is forced to accept under optimal play, where Bob then picks a disjoint block of k.
- Level
Medium7 of 10
- Topics
- Sliding window, Prefix sum, Greedy, Binary search
- Solved
- No attempts yet
Problem
Alice and Bob have won a television quiz show, and now they must choose their prizes. There are n prizes available, numbered from 1 to n.
The prizes are distributed as follows. The show's organizers tell the winners a positive integer k (1 ≤ k ≤ n / 3). First Alice chooses any k consecutive prize numbers. Then Bob chooses k consecutive prize numbers, and he cannot choose numbers that Alice has already chosen. After that, the winners take the prizes they chose.
Alice knows Bob well, and she has found out the value of each prize to Bob, which is a positive integer. Alice is angry at Bob and wants to choose her prizes so that the total value of the prizes Bob gets is as small as possible. Alice does not care which prizes she gets.
Given the values of the prizes and the value of k, write a program that determines the smallest x for which Alice can ensure that Bob cannot choose prizes with total value greater than x.
Input
The first line of the input contains two integers: n, the total number of prizes, and k, the number of consecutive prize numbers each winner must choose (3 ≤ n ≤ 100 000, 1 ≤ k ≤ n / 3).
The second line contains n positive integers: a1, a2, …, an. For each prize, this is its value to Bob (1 ≤ ai ≤ 109).
Output
Output a single number: the smallest x for which Alice can ensure that Bob cannot choose prizes with total value greater than x.
Hint
In the given example, Alice can choose the 4th and 5th prizes. Then it is optimal for Bob to choose the 9th and 10th prizes, with total value 7.