25018번 - 히스토그램 서브태스크점수언어 제한함수 구현

밑변이 바닥에 평행한 직사각형 $N$개가 바닥에 연속하게 붙어 있는 형태의 히스토그램을 생각해 보자. 각 직사각형은 너비가 1로 동일하며 왼쪽에서 $i$ $(1 \le i \le N)$번째 직사각형의 높이는 정수 $H_i$이다.

아래 그림은 가능한 히스토그램의 한 예를 나타낸다.

이 히스토그램 내부에서 밑변이 바닥에 평행하고 서로 꼭짓점 및 모서리를 제외한 영역이 겹치지 않으며 각 변이 정수 길이를 가지는 직사각형들을 $K$개 이하로 구해, 구한 직사각형들의 넓이의 합이 최대가 되게 하려고 한다. 이 값을 $f(K)$라고 하자.

$f(1)$, $f(2)$, $f(3)$을 구하는 프로그램을 작성하여라.

여러분은 아래 함수를 구현해야 한다.

vector<long long> max_area(vector<int> H)

• 이 함수는 단 한 번만 호출된다.
• 인자로 주어지는 정수 배열 H의 크기는 $N$이다. 배열의 각 원소 H[$i$]는 왼쪽에서 $i+1$번째 직사각형의 높이 $H_{i+1}$을 나타낸다. $(0 \le i \le N - 1)$
• 이 함수는 크기가 1 이상 3 이하인 배열 A를 반환해야 한다. A[$i$]에는 $f(i+1)$을 저장해야 한다. $(0 \le i < |$A$|)$ 배열 A의 크기에 따라 채점 기준이 다름에 유의하라.

제출하는 소스 코드의 어느 부분에서도 입출력 함수를 실행해서는 안 된다.

• $1 \le N \le 500\,000$
• $1 \le H_i \le 500\,000$ $(1 \le i \le N)$

• $H_i \le H_{i+1}$ $(1 \le i \le N - 1)$
• $|$A$|=3$이고, $f(1)$, $f(2)$, $f(3)$이 모두 정확하다면 10점을 받는다.

• $N \le 500$
• $|$A$|=3$이고, $f(1)$, $f(2)$, $f(3)$이 모두 정확하다면 3점을 받는다.

• $N \le 5\,000$
• $|$A$|=2$이고, $f(1)$, $f(2)$이 모두 정확하다면 3점을 받는다.
• $|$A$|=3$이고, $f(1)$, $f(2)$, $f(3)$이 모두 정확하다면 15점을 받는다.

• $N \le 200\,000$
• $|$A$|=2$이고, $f(1)$, $f(2)$이 모두 정확하다면 7점을 받는다.
• $|$A$|=3$이고, $f(1)$, $f(2)$, $f(3)$이 모두 정확하다면 27점을 받는다.

• 추가적인 제약 조건이 없다.
• $|$A$|=1$이고, $f(1)$이 정확하다면 1점을 받는다.
• $|$A$|=2$이고, $f(1)$, $f(2)$이 모두 정확하다면 15점을 받는다.
• $|$A$|=3$이고, $f(1)$, $f(2)$, $f(3)$이 모두 정확하다면 45점을 받는다.

max_area 함수가 반환한 배열을 A라고 하자.

A의 크기가 1 이상 3 이하가 아닌 경우 0점을 받는다.

부분문제의 기준에 의해, $f(1)$, $\cdots$, $f(|$A$|)$의 값들 중 하나라도 정확하지 않은 값이 있다면 0점을 받는다는 점에 유의하라.

$f(1)$, $\cdots$, $f(|$A$|)$의 값이 모두 정확한 경우 각 부분문제의 점수 기준에 따른 점수를 받을 수 있다.

위의 기준에서 "$f(i)$가 정확하다"는 것은, A의 크기가 $i$ 이상이고 A[$i-1$]의 값이 $f(i)$와 같다는 것을 의미한다.

각 부분문제의 점수는 그 부분문제의 모든 데이터에 대한 점수 중 최솟값임에 유의하라.

$N = 7$, $H =$ [3, 2, 1, 2, 1, 4, 3] 인 경우를 생각해 보자. 

그레이더는 다음 함수를 호출한다.

max_area([3, 2, 1, 2, 1, 4, 3]) = [7, 11, 13]

아래 3개의 그림은 각각 1, 2, 3의 $K$에 대해 넓이의 합이 최대인 경우 중 하나를 나타낸다.

max_area 함수가 [7, 11]을 반환한 경우, $f(1)$과 $f(2)$가 정확하기에 각 부분문제의 점수 기준에 따른 점수를 받을 수 있다.

max_area 함수가 [7, 12, 13]를 반환한 경우, $f(1)$과 $f(3)$이 정확함에도 $f(2)$가 잘못되었기에 0점을 받음에 유의하라.

max_area 함수가 [7, 11, 14]를 반환한 경우, $f(1)$과 $f(2)$이 정확함에도 $f(3)$가 잘못되었기에 0점을 받음에 유의하라.

이 예제는 부분문제 2, 3, 4, 5의 조건을 만족한다.

$N = 7$, $H =$ [1, 2, 3, 4, 5, 6, 7] 인 경우를 생각해 보자. 

그레이더는 다음 함수를 호출한다.

max_area([1, 2, 3, 4, 5, 6, 7]) = [16, 21, 24]

이 예제는 모든 부분문제의 조건을 만족한다.

$N = 5$, $H =$ [1, 3, 4, 3, 1] 인 경우를 생각해 보자. 

그레이더는 다음 함수를 호출한다.

max_area([1, 3, 4, 3, 1]) = [9, 11, 12]

이 예제는 부분문제 2, 3, 4, 5의 조건을 만족한다.

Sample grader는 아래와 같은 형식으로 입력을 받는다.

• Line 1: $N$
• Line 2: $H_1$ $H_2$ $\cdots$ $H_N$

Sample grader는 다음을 출력한다.

• Line 1 + $i$ $(0 \le i < |$A$|)$: max\_area 함수가 반환한 배열 A에 대해, A[$i$]의 값

Sample grader는 실제 채점에서 사용하는 그레이더와 다를 수 있음에 유의하라.

• histogram_public.zip