Problemas
N 열로 구성된 조각이 아래 그림과 같이 주어진다.
위 예시 그림에서는 N = 6 이고, 각 열의 높이는 [ 2, 4, 3, 2, 1, 3 ] 이다.
정올이는 "하나의 연결된 조각" 을 이 위에 붙여서 직사각형을 만드려고 한다.
예를 들어, 아래와 같이 할 수 있다.
이 때 정올이가 사용한 녹색 조각의 크기는 27 이다. ( 조각의 크기는, 그 조각에 포함된 단위 칸들의 개수다. )
아래는 불가능한 경우다.
위 그림이 불가능한 이유는, 녹색 조각이 하나로 연결되어 있지 않기 때문이다.
즉, 조건을 만족하며 직사각형을 만드는 가장 작은 조각은 아래 그림과 같다.
이 조각의 크기는 15 이고, 이 값이 최소다.
직사각형을 만드는 가장 작은 조각의 크기를 찾는 프로그램을 작성하자.
Entrada
첫 줄에 N 이 입력된다. ( 3 ≤ N ≤ 100,000 )
두 번째 줄에 각 열의 높이가 차례대로 입력된다. ( 1 이상 109 이하의 정수 )
모든 열의 높이가 같은 입력은 주어지지 않는다. ( 입력 도형은 직사각형이 될 수 없다. )
Salida
조건을 만족하는 가장 작은 조각의 크기를 출력한다.
Subtarea
| # | Puntaje | Condición |
|---|---|---|
| #1 | 20 | N = 3 |
| #2 | 20 | 입력된 N개의 정수들이 모두 다르다. |
| #3 | 20 | 1 ≤ N ≤ 1,000 |
| #4 | 40 | 제약 조건 없음 |
Ejemplo #1
6
2 4 3 2 1 3
15
Ejemplo #2
5
2 2 1 1 2
2
3번째, 4번째 열에 각각 1 칸을 채워 넣으면 된다.
( 하나의 연결된 조각이 되기에 조건을 만족한다. )
Ejemplo #3
5
2 1 2 1 2
7
하나의 조각으로 높이 2 짜리 직사각형을 만들 순 없다. ( 두 번째 열과 네 번째 열은 서로 떨어져 있기 때문 )
따라서 높이 3 짜리 직사각형을 만들어야 하고, 이 때의 답은 7 이다.
Pista
Debes iniciar sesión para escribir código.