C - Planting the Flower Bed Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 366 点

問題文

高橋君は公園の花壇の管理を任されています。花壇には N 株の花を植える必要があります。

花壇には M 個の植え付けポイントが一直線上に並んでおり、左から順にポイント 1 、ポイント 2 、...、ポイント M と番号が付けられています。ポイント i とポイント i+1 の間の距離は D_i メートルです。各ポイントには最大 1 株の花しか植えられません。

高橋君は、花を植えるポイントを N 個選ぶ必要があります。花壇の見栄えを良くするため、選んだポイントのうち最も左にあるポイントと最も右にあるポイントの間の距離が、できるだけ大きくなるようにしたいと考えています。

さらに、花同士が近すぎると根が競合して成長に悪影響があります。そこで、選んだ N 個のポイントのうち、隣り合うポイント同士（選んだポイントの中で左から i 番目と i+1 番目）の距離の最小値が K メートル以上でなければならないという制約があります。

条件を満たすように N 個のポイントを選んだとき、最も左にあるポイントと最も右にあるポイントの間の距離の最大値を求めてください。条件を満たす選び方が存在しない場合は -1 を出力してください。

制約

  • 2 \leq M \leq 5 \times 10^5
  • 1 \leq N \leq M
  • 1 \leq K \leq 10^{15}
  • 1 \leq D_i \leq 10^9 (1 \leq i \leq M-1)
  • 入力はすべて整数

入力

N M K
D_1 D_2 ... D_{M-1}
  • 1 行目には、植える花の株数を表す N 、ポイントの個数を表す M 、隣り合うポイントの距離の最小値の下限を表す K が、スペース区切りで与えられる。
  • 2 行目には、ポイント i とポイント i+1 の間の距離を表す D_i が M - 1 個、スペース区切りで与えられる。

出力

条件を満たすように N 個のポイントを選んだとき、最も左にあるポイントと最も右にあるポイントの間の距離の最大値を 1 行で出力せよ。条件を満たす選び方が存在しない場合は -1 を出力せよ。

入力例 1

3 5 4
2 3 4 5

出力例 1

14

入力例 2

2 4 100
10 20 30

出力例 2

-1

入力例 3

5 12 10
3 7 2 8 6 4 10 5 9 1 12

出力例 3

67

入力例 4

10 30 15
8 7 10 5 12 6 9 11 4 13 7 8 15 3 14 6 10 9 5 12 8 7 11 4 16 6 9 10 5

出力例 4

250

入力例 5

1 2 1000000000000000
1

出力例 5

0

Score : 366 pts

Problem Statement

Takahashi is in charge of managing a flowerbed in a park. He needs to plant N flowers in the flowerbed.

In the flowerbed, there are M planting points arranged in a straight line, numbered Point 1, Point 2, ..., Point M from left to right. The distance between Point i and Point i+1 is D_i meters. At most one flower can be planted at each point.

Takahashi needs to choose N points to plant the flowers. To make the flowerbed look visually appealing, he wants to maximize the distance between the leftmost and rightmost chosen points.

Furthermore, if the flowers are too close to each other, their roots will compete and negatively affect their growth. Therefore, there is a constraint that among the N chosen points, the distance between any two adjacent chosen points (the i-th and (i+1)-th points from the left among the chosen points) must be at least K meters.

Find the maximum possible distance between the leftmost and rightmost points when choosing N points that satisfy the conditions. If there is no choice of points that satisfies the conditions, output -1.

Constraints

  • 2 \leq M \leq 5 \times 10^5
  • 1 \leq N \leq M
  • 1 \leq K \leq 10^{15}
  • 1 \leq D_i \leq 10^9 (1 \leq i \leq M-1)
  • All input values are integers.

Input

N M K
D_1 D_2 ... D_{M-1}
  • The first line contains N, the number of flowers to plant, M, the number of points, and K, the minimum required distance between adjacent points, separated by spaces.
  • The second line contains M - 1 integers D_i, representing the distance between Point i and Point i+1, separated by spaces.

Output

Print the maximum distance between the leftmost and rightmost points among the chosen N points satisfying the conditions in a single line. If no valid choice exists, print -1.

Sample Input 1

3 5 4
2 3 4 5

Sample Output 1

14

Sample Input 2

2 4 100
10 20 30

Sample Output 2

-1

Sample Input 3

5 12 10
3 7 2 8 6 4 10 5 9 1 12

Sample Output 3

67

Sample Input 4

10 30 15
8 7 10 5 12 6 9 11 4 13 7 8 15 3 14 6 10 9 5 12 8 7 11 4 16 6 9 10 5

Sample Output 4

250

Sample Input 5

1 2 1000000000000000
1

Sample Output 5

0