左右の長さが L [cm] のようかんがあります。 N 個の切れ目が付けられており、左から i 番目の切れ目は左から A(i)[cm] の位置にあります。あなたは N 個の切れ目のうち K 個を選び、ようかんを K+1 個のピースに分割したいです。そこで、以下の値を スコア とします。K+1 個のピースのうち、最も短いものの長さ（cm 単位) スコアが最大となるように分割する場合に得られるスコアを求めてください。
制約
1≤K≤N≤100000
0<A(1)<A(2)​<⋯<A(N)<L≤10^9
入力はすべて整数

入力
入力は以下の形式で標準入力から与えられます。
```
N L
K
A(1) A(2) ⋯ A(N)
```​	

出力
求めるスコアを出力してください。

入力例 1
```
3 34
1
8 13 26
```
出力例 1
```
13
```
左から 2 番目の切れ目で分割すると、長さ 13 [cm] のピースと長さ 21 [cm] のピースに分かれ、スコア 13 を達成できます。

入力例 2
```
7 45
2
7 11 16 20 28 34 38
```
出力例 2
```
12
```
左から 3 番目と 5 番目の切れ目で分割すると、スコア 12 を達成できます。

入力例 3
```
3 100
1
28 54 81
```
出力例 3
```
46
```
左から 2 番目の切れ目で分割すると、スコア 46 を達成できます。

入力例 4
```
3 100
2
28 54 81
```
出力例 4
```
26
```
入力例 5
```
20 1000
4
51 69 102 127 233 295 350 388 417 466 469 523 553 587 720 739 801 855 926 954
```
出力例 5
```
170
```

この問題は二分探索を用いて解くことができます。まず、スコアの最小値と最大値を設定します。最小値は1、最大値はようかんの長さLです。次に、最小値と最大値の中間値を計算し、その値をスコアとして分割可能かどうかを確認します。分割可能であれば、スコアを上げて再度確認します。分割不可能であれば、スコアを下げて再度確認します。このプロセスを最小値と最大値が逆転するまで繰り返します。

以下にPythonでの実装例を示します。

def solve():
    N, L = map(int, input().split())
    K = int(input())
    A = list(map(int, input().split()))
    A.append(L)
    B = [A[0]] + [A[i+1] - A[i] for i in range(N)]
    
    left = -1
    right = L + 1
    while right - left > 1:
        mid = (left + right) // 2
        cnt = 0
        tmp = 0
        for i in range(N+1):
            if tmp + B[i] >= mid:
                cnt += 1
                tmp = 0
            else:
                tmp += B[i]
        if cnt >= K + 1:
            left = mid
        else:
            right = mid
    print(left)

solve()
このコードは、入力を受け取り、ようかんの各部分の長さを計算し、二分探索を行って最適なスコアを見つけ出します。最後に、最適なスコアを出力します。

この問題は二分探索を使用して解くことができます。スコアが最大となるように分割するためには、最も短いピースの長さを最大化する必要があります。これは、各ピースの長さが特定の値以上であるように分割することが可能かどうかを確認することで達成できます。

以下に、この問題を解くためのPythonコードを示します。

```python
def check(mid, A, K, L):
    cnt = 0
    pre = 0
    for i in range(len(A)):
        if A[i] - pre >= mid and L - A[i] >= mid:
            cnt += 1
            pre = A[i]
    if cnt >= K:
        return True
    return False

def solve():
    N, L = map(int, input().split())
    K = int(input())
    A = list(map(int, input().split()))
    left = 0
    right = L
    while right - left > 1:
        mid = (left + right) // 2
        if check(mid, A, K, L):
            left = mid
        else:
            right = mid
    print(left)

solve()
```

このコードでは、まず`check`関数を定義しています。この関数は、与えられた長さ`mid`でようかんを分割することが可能かどうかを確認します。次に、`solve`関数では二分探索を行い、可能な最大の長さを見つけ出します。

この問題は、特定の制約の下での最適な切断方法を見つけることを目的としています。スコアはK+1個のピースのうち最も短いものの長さで、このスコアを最大化するような切断方法を見つける必要があります。これは二分探索アルゴリズムを使用して効率的に解決できる問題です。

アルゴリズムの大まかな流れは以下の通りです：

切断可能な最小のピースの長さ（最低スコア）と最大のピースの長さ（最高スコア）を決定します。
これらの値を基にして、可能なスコアの範囲を二分探索します。
あるスコアが達成可能かどうかを判断するために、与えられた切断位置を利用します。
最終的に、最大の達成可能なスコアを見つけます。
まずは、二分探索を実装し、与えられた例でテストしてみましょう。
アルゴリズムが正しく機能していることが確認できました。与えられた例でテストした結果は以下の通りです：

入力例1: 3 34 1 [8, 13, 26] の出力は 13 です。
入力例2: 7 45 2 [7, 11, 16, 20, 28, 34, 38] の出力は 12 です。
入力例3: 3 100 1 [28, 54, 81] の出力は 46 です。
入力例4: 3 100 2 [28, 54, 81] の出力は 26 です。
入力例5: 20 1000 4 [51, 69, 102, 127, 233, 295, 350, 388, 417, 466, 469, 523, 553, 587, 720, 739, 801, 855, 926, 954] の出力は 170 です。
これらの結果は、問題で与えられた出力例と一致しています。よって、このアルゴリズムは問題を解決するために適切です。 ​​
```
def max_score(N, L, K, cuts):
    def is_possible(score):
        """ Check if a given score is possible with the current cuts """
        count, last_cut = 0, 0
        for cut in cuts:
            if cut - last_cut >= score and L - cut >= score:
                count += 1
                last_cut = cut
                if count == K:
                    return True
        return False

    low, high = 0, L
    while low < high:
        mid = (low + high + 1) // 2
        if is_possible(mid):
            low = mid
        else:
            high = mid - 1
    return low

# Test the function with the provided examples
example1 = max_score(3, 34, 1, [8, 13, 26])
example2 = max_score(7, 45, 2, [7, 11, 16, 20, 28, 34, 38])
example3 = max_score(3, 100, 1, [28, 54, 81])
example4 = max_score(3, 100, 2, [28, 54, 81])
example5 = max_score(20, 1000, 4, [51, 69, 102, 127, 233, 295, 350, 388, 417, 466, 469, 523, 553, 587, 720, 739, 801, 855, 926, 954])

example1, example2, example3, example4, example5
```