Races#7174
A cyclist is preparing for mountain time trial races (i.e., against the clock). He has estimated his expected rate of energy expenditure (i.e., power) as a function of time after the race start, and wants to devise a nutrition plan for the entire duration of the race. The cyclist's only source of energy will be carbohydrates in nutrition bars, each identical and containing two types of carbohydrates: fast-digesting (mono- and disaccharides) and slow-digesting (polysaccharides).
The effect of consuming one bar can be modeled as follows: for the first t_1 seconds after consumption, the bar allows the cyclist to generate milliwatts of power ("fast" carbohydrates); for the next t_2 seconds, the bar provides milliwatts of power ("slow" carbohydrates). After this period, the effect of the bar is completely gone. For simplicity, assume:
The model of carbohydrate digestion and utilization is linear, i.e., the powers from consuming different bars at any moment in time simply add up.
Energy surpluses do not accumulate.
The cyclist may consume bars instantly at any moment during or before the race.
Find the minimum number of bars needed to meet the cyclist's energy requirements for the entire race duration.
The first line contains five integers , t_1, t_2, , —the expected duration of the race in seconds and the bar parameters, where 1 \le n, t_1, t_2 \le 10^5, 1 \le a, b \le 10^9.
The second line contains integers p_0, p_1, \ldots, p_{n-1}, where 1 \le p_j \le 10^9—the required power level for the -th second after the race start.
Output a single integer—the minimum number of bars needed.
Example 1