연습문제

탑의 높이

난이도
Lv. 4
제출
177 명
참가자
43 명
정답률
28.79 %
지원 언어
C
C++
Java
Python
Rust
언어별 시간/메모리
언어별 시간/메모리 표
언어 시간 메모리
Java 3초 1024MB
Python 3초 1024MB
C 2초 1024MB
C++ 2초 1024MB
Rust 2초 1024MB

당신의 회사는 대륙간 통신을 처리하거나, 우주 엘리베이터의 건설 등에 이용할 수 있도록, 지상에서부터 높은 탑을 쌓았다. 이 탑은 총 개의 기둥이 일렬로 놓여 있는 형태이며, 왼쪽에서부터 번째 기둥의 높이는 이다.

탑의 안정성을 위해, 두 인접한 기둥의 높이 차이는 이하이다. 즉, 모든 에 대해, 이다.

탑의 높이는 가장 높은 기둥의 높이로 정의한다. 즉, 중 최댓값 (가장 큰 값)을 탑의 높이로 한다.

당신의 회사는 탑의 높이를 최대한 높이고 싶다. 탑을 새로 건설할 수는 없으므로, 각각의 기둥의 높이를 높일 수밖에 없다. 당신은 아래와 같은 연산을 최대 회 수행할 수 있다.

  • 기둥 하나를 정해서, 높이를 증가시킨다.

탑은 높이를 높인 이후에도 안정성을 유지해야 하기 때문에, 항상 두 인접한 기둥의 높이 차이는 이하여야 한다.

최적의 연산을 통해 얻을 수 있는 탑의 최대 높이를 구하는 프로그램을 작성하라.

제약조건

[문제 제약 조건]

[조건 1] 주어지는 모든 수는 정수이다.

[조건 2]

[조건 3]

[조건 4] 모든 에 대해,


[서브 태스크별 제약 조건]

Subtask1 (10점): ,

Subtask2 (20점): ,

Subtask3 (30점):

Subtask4 (40점): 추가 제약 조건 없음

입력형식

첫 번째 줄에 두 정수 과 가 공백으로 구분되어 주어진다.

두 번째 줄에 개의 정수 이 공백으로 구분되어 주어진다.

출력형식

첫 번째 줄에 최대 높이를 출력한다.

입력예제1

5 4
2 2 2 2 2
출력예제1

4

아래와 같이 총 4번의 연산으로 높이를 로 만들 수 있다.

•2 2 2 2 2

•2 3 2 2 2

•2 3 3 2 2

•2 3 3 3 2

•2 3 4 3 2

입력예제2

7 10
1 2 3 4 3 2 1
출력예제2

6

입력예제3

8 12
1 2 3 4 3 2 1 2
출력예제3

7

목록