Bessie the cow has designed what she thinks will be the next big hit video game:
"Angry Cows". The premise, which she believes is completely original, is that
the player shoots cows with a slingshot into a one-dimensional scene consisting
of a set of hay bales located at various points on a number line. Each cow lands
with sufficient force to detonate the hay bales in close proximity to her
landing site. The goal is to use a set of cows to detonate all the hay bales.

There are \(N\) hay bales located at distinct integer positions
\(x_1, x_2, \ldots, x_N\) on the number line. If a cow is launched with power \(R\)
landing at position \(x\), this will causes a blast of "radius \(R\)", destroying
all hay bales within the range \(x-R \ldots x+R\).

A total of \(K\) cows are available to shoot, each with the same power \(R\). Please
determine the minimum integer value of \(R\) such that it is possible to use the \(K\) cows
to detonate every single hay bale in the scene.

Problem credits: Brian Dean

Problem credits: Brian Dean

The first line of input contains \(N\) (\(1 \leq N \leq 50,000\)) and \(K\)
(\(1 \leq K \leq 10\)). The remaining \(N\) lines all contain integers
\(x_1 \ldots x_N\) (each in the range
\(0 \ldots 1,000,000,000\)).

Please output the minimum power \(R\) with which each cow must be launched in order
to detonate all the hay bales.

riseoj 작성

출처 올림피아드 > USACO > 2015-2016 > January > Silver