DMOPC '21 Contest 2 P4 - Water Mechanics

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 2.0s
Memory limit: 256M

Problem types

Keenan recently bought a new game, and he wants to show it to you!

Keenan's game consists of N cells in a row, of varying height. Keenan also has many water buckets, and he wants to fill every cell with water.

However, as Keenan explains, water mechanics in this game are a bit weird. There is an integer K chosen by the game, where water can flow at most K units on equal-height cells. Specifically, if Keenan pours his bucket into a cell i, the water can flow in both directions, filling all cells until cells i - K and i + K with water before it loses momentum. However, if the water descends from a higher elevation to a lower one, this limit is reset to K, and the water can continue flowing as if it had just been poured into the lower cell. Water can never flow from a lower elevation to a higher one.

Keenan wants to fill all his cells with water, but he doesn't want to use that many buckets. Can you tell him the minimum number of cells he has to pour his bucket into so that all cells are filled with water?


1 \le K \le N \le 10^6

1 \le h_i \le 10^9

Subtask 1 [30%]

1 \le N \le 3 \times 10^3

Subtask 2 [70%]

No additional constraints.

Input Specification

The first line will contain two space-separated integers, N and K.

The next line will contain N space-separated integers, h_i, the heights of the cells, in order.

Output Specification

Output the minimum number of cells Keenan has to pour into in order to fill the entire row of cells with water.

Sample Input

6 1
3 3 3 4 4 7

Sample Output



If we pour into the second and sixth cells, we can fill all the cells in 2 moves, which we can prove to be minimal.

Note that if we pour water into the third cell, it would not reach the first cell.


There are no comments at the moment.