5276 : A77 - 양갱 파티 (★4)
•시간제한: 2.000 S
•메모리제한: 1024 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
좌우 길이가 $L$ [cm]인 양갱이 있습니다. $N$ 개의 절취선이 있으며, 왼쪽에서 $i$ 번째 절취선은 왼쪽에서 $A_i$ [cm] 지점에 있습니다.
당신은 $N$ 개의 절취선 중 $K$ 개를 선택하여 양갱을 $K+1$ 개의 조각으로 나누려고 합니다. 이때 다음 값을 점수라고 합니다.
점수가 최대가 되도록 나눌 때 얻을 수 있는 점수를 구하세요.
[제약 조건]
• $1 \le K \le N \le 100000$
• $0 \lt A_1 \lt A_2 \lt \cdots \lt A_N \lt L \le 10^9$
• 입력되는 모든 값은 정수입니다.
당신은 $N$ 개의 절취선 중 $K$ 개를 선택하여 양갱을 $K+1$ 개의 조각으로 나누려고 합니다. 이때 다음 값을 점수라고 합니다.
- $K+1$ 개의 조각 중 가장 짧은 조각의 길이 (cm 단위)
점수가 최대가 되도록 나눌 때 얻을 수 있는 점수를 구하세요.
[제약 조건]
• $1 \le K \le N \le 100000$
• $0 \lt A_1 \lt A_2 \lt \cdots \lt A_N \lt L \le 10^9$
• 입력되는 모든 값은 정수입니다.
입력 설명
첫째 줄에 $N, L$ 이 주어집니다.
둘째 줄에 $K$ 가 주어집니다.
셋째 줄에 절취선의 위치 $A_1, \ldots, A_N$ 이 주어집니다.
둘째 줄에 $K$ 가 주어집니다.
셋째 줄에 절취선의 위치 $A_1, \ldots, A_N$ 이 주어집니다.
출력 설명
가능한 최대 점수를 출력하세요.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
3 34
1
8 13 26
출력 예시
COPY
복사되었습니다!
복사되었습니다!
13