Waterloo 2023 Fall E - Loose Goose

View as PDF

Submit solution

Points: 25
Time limit: 1.5s
Memory limit: 256M

Problem type

Competitive programming is awesome, but bartending can be a better way to make some extra cash. Tonight you're bartending at the "Lonely Goose" bar at Waterloo, serving their signature "Lonely Goose" cocktail. There are n glasses lined up in a row at a bar table. Initially, all glasses are empty and the goal is to have a_i millilitres of "Lonely Goose" in the i-th glass. You're a skilled bartender, and each minute you can choose a contiguous set of glasses and pour either one millilitre of cocktail into each glass or x millilitres into each glass. It is forbidden to pour out excess liquid from a glass (which would be wasteful).

Find out the quickest time in which you can achieve the desired drink allocation.

Input Specification

The first row contains two integers - n and x. The next row contains n integers a_i.

1 \le n \le 300\,000, 2 \le x \le 10^{9}, 0 \le a_i \le 10^{9}

Output Specification

Output a single number - the smallest possible number of minutes to achieve the goal.

Sample Input 1

6 3
1 1 1 4 3 3

Sample Output 1


Explanation for Sample 1

In the first test, you can pour 1 millilitre into glasses 1-4, followed by pouring 3 millilitres into glasses 4-6.

Sample Input 2

5 5
4 0 4 0 4

Sample Output 2



There are no comments at the moment.