Construction (Editorial)

We’ll search for the desired pier length d using binary search. Initially, let d \in [Left; Right] = [0; INF].

Let us consider the following subproblem: is it possible to build a pier consisting of exactly $m$ planks, each of length Mid = (Left + Right) / 2 ? To check this, calculate how many planks of length $Mid$ can be obtained from the available ones.

From a plank of length l_i, we can obtain \lfloor l_i / Mid \rfloor planks of length $Mid$. By summing this value over all planks, we get the total number of planks of length $Mid$ that can be obtained through cutting:

If the total number is at least $m$, it means we can try to increase the length — so we set Left = Mid + 1. Otherwise, reduce the upper bound: Right = Mid.

The final answer will be Left - 1.

Example

In the given example, there are $4$ planks. The task is to build a pier consisting of $6$ planks.

If we choose the plank length to be $8$, then from the available planks we can obtain

planks of length $8$.

If we choose the length to be $9$, then we get

planks, which is less than the required amount.

Algorithm implementation

Let's define the constants used. The lengths of the available planks l_i are stored in the array $a$.

#define INF 2000000010
#define MAX 1000009
long long a[MAX];

The function cnt returns the number of planks that can be obtained from the available ones if each plank must have an exact length of $Mid$. This value is equal to the sum of

long long cnt(long long  Mid) 
{
  if (Mid == 0) return INF;
  long long res = 0;
  for(i = 0; i < n; i++)
    res += a[i] / Mid;
  return res;
}

The main part of the program. Read the input data.

scanf("%d %d",&n,&m);
for(i = 0; i < n; i++)
  scanf("%d",&a[i]);

Set the boundaries for the value of d \in [Left; Right] = [0; INF] and start a binary search.

Left = 0;
Right = INF;
while (Left < Right)
{
  Mid = (Left + Right) / 2;

The value of cnt(Mid) is the number of boards that can be obtained from the available ones if each must have length $Mid$. If this number is less than the required $m$, the proposed board length should be decreased by setting Right = Mid. Otherwise, increase the lower boundary by setting Left = Mid + 1.

  if (cnt(Mid) < m) Right = Mid;
  else Left = Mid + 1;
}

Print the answer.

printf("%lld\n",Left - 1);