시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 1024 MB 70 36 27 60.000%

문제

무수히 넓은 우주에서는 한 국가의 영역을 결정하기 위해, 특이한 땅따먹기 게임을 한다고 전해진다. 이 게임은 N개의 막대쌍과 3개의 슬롯을 가지고 진행된다. 막대쌍은 위아래로 차례로 쌓여있으며, 맨 위의 막대쌍을 제외한 다른 막대기는 건드릴 수 없다.

참가자는 아래 2가지 중 하나를 선택하여 행동하는 것을 원하는 만큼 반복할 수 있다.

  • 맨 위에 있는 막대쌍 하나를 가져와 비어있는 슬롯에 보관한다.
  • 슬롯에 보관되어 있는 막대쌍 두 개를 꺼내어, 각 막대기를 변으로 하는 직사각형을 만들고 그 직사각형으로 둘러쌓인 공간을 영역으로 인정받는다.

그렇게 만들어진 모든 직사각형 영역의 넓이의 합이 그 국가의 면적이 된다. 맨 위에 있는 막대쌍을 슬롯에 넣지 않고 버리거나, 슬롯에 있는 막대쌍을 임의로 버릴 수 없다. 모든 행동은 주어진 선택지 두 가지 중 하나여야 한다.

이번에는 희권국의 영역을 결정할 차례이다. 희권이가 N개의 막대쌍의 순서와 길이를 전부 알고 있다고 할 때, 희권국이 인정받을 수 있는 영역의 총면적의 최댓값은 얼마일까?

입력

첫째 줄이 N (2 ≤ N ≤ 3000)이 주어진다.

둘째 줄에 위에서부터 i번째에 있는 막대쌍의 길이를 나타내는 정수 Ai (1 ≤ Ai ≤ 106)가 공백으로 구분되어 주어진다.

출력

희권국이 인정받을 수 있는 영역의 총면적의 최댓값을 나타내는 정수를 출력하시오.

예제 입력 1

4
4 2 3 4

예제 출력 1

22

슬롯에 길이 4, 2, 3의 막대쌍을 순서대로 넣는다. 막대쌍 2와 3을 사용하여 넓이 6의 직사각형을 만들고, 길이 4의 막대쌍을 슬롯에 보관하고 길이 4의 막대쌍 두개로 넓이 16의 직사각형을 만드는 것이 최적이다.

예제 입력 2

3
10 10 5

예제 출력 2

100

길이 10, 10의 막대쌍을 슬롯에 넣고 넓이 100의 직사각형을 만드는 것이 최적 중 하나이다.

예제 입력 3

10
793299 221125 31727 661308 191447 485566 55256 823436 202614 328742

예제 출력 3

1008649459763

출처

University > 인천대학교 > INU 코드페스티벌 2020 G번