시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 457 | 237 | 163 | 50.621% |
알렉스는 창고에서 어렸을 때 가지고 놀던 막대 N개를 찾았다. 막대의 길이는 A1, A2, ..., AN이며, 모두 2보다 크거나 같은 자연수이다.
오늘은 이 막대를 이용해서 직사각형을 만들려고 한다. 각 막대는 최대 한 번 사용할 수 있고, 여러 개의 막대를 이용해서 직사각형의 한 변을 만드는 것은 불가능하다. 일부 막대는 직사각형을 만들 때 사용하지 않아도 된다. 직사각형은 하나 이상을 만들어도 된다.
알렉스는 막대의 길이를 1만큼만 줄일 수 있는 기계를 하나 만들었다. 막대의 길이가 Ai라면, 막대의 길이를 Ai-1로 줄여서 사용할 수 있다. 기계를 사용하는 횟수는 제한이 없지만, 길이를 줄인 막대를 또 줄일 수는 없다.
알렉스는 만든 직사각형의 넓이의 합이 최대가 되게 직사각형을 만들려고 한다. 이 때, 그 넓이를 구하는 프로그램을 작성하시오.
첫째 줄에 막대의 개수 N(1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄에는 막대의 길이 A1, A2, ..., AN이 주어진다. (2 ≤ Ai ≤ 100,000)
알렉스가 만든 직사각형의 넓이의 합의 최댓값을 출력한다.
4 5 5 6 6
30
4 4 5 2 3
8
변의 길이가 2, 4인 직사각형을 만들 수 있다.
4 2 4 6 8
0
6 5 6 6 3 4 4
24
9 10 3 4 4 4 5 6 6 6
42
길이가 5, 6, 6, 6인 막대 중에서 길이가 6인 막대 하나의 길이를 5로 줄여 넓이가 30인 직사각형을 만들 수 있다. 그 다음, 길이가 3, 4, 4, 4인 막대 중에서 길이가 4인 막대 하나의 길이를 3으로 줄여 넓이가 12인 직사각형을 만들 수 있다.
이 외의 다른 방법은 넓이의 합이 42를 넘지 않는다.
10 10 10 10 10 10 10 10 10 10 10
200
4 100000 100000 100000 100000
10000000000