24934번 - Similar Spacing 다국어

Finally, your dream of owning a restaurant chain has come true! You have consulted a marketing firm and received instructions on how to best place your restaurants in the city.

The firm has identified potential restaurant sites along a single road, each of which can house a single restaurant. To maximize influencer media impact, you have been advised to build some restaurants along this road and open them all at the same time. Apparently, the best way to attract customers to your chain is to build all of your restaurants with similar spacing along the road; such placement maximizes pedestrian recall coherence, which is all the rage in marketing.

Specifically, if $a$ is the maximum distance between any two adjacent restaurants and $b$ is the minimum distance between any two adjacent restaurants, place your restaurants such that $a-b$ is minimized.

The first line of input contains two integers $N$ and $K$ (with $2≤N≤100$ and $2≤K≤N$) where $N$ is the number of potential restaurant sites, and $K$ is the number of restaurants to build. The second line of input contains $N-1$ integers $d_1,\dots ,d_{N-1}$ (with $0≤d_i<2^{31}$) where $d_i$ is the distance between restaurant site $i$ and $i+1$.

Display the number $a-b$.

In Sample Input 2, an optimal solution could place restaurants at sites $1$, $3$, $5$, and $6$. With this placement the distances between adjacent restaurants are $d_1+d_2$, $d_3+d_4$, and $d_5$, respectively. So, $a=10$ (the maximum of these), $b=8$ (the minimum), and $a-b=2$.

In Sample Input 3, an optimal solution could place restaurants at sites $3$, $4$, $6$, $7$, and $8$. With this placement the distances between adjacent restaurants are $d_3$, $d_4+d_5$, $d_6$, and $d_7$, respectively. So, $a=32$, $b=18$, and $a-b=14$.