[BOJ 16207] 직사각형
View as PDF
Submit solution
Points:
3
Time limit:
2.0s
Memory limit:
512M
Problem types
Allowed languages
Assembly, Awk, C, C++, Java, Pascal, Perl, Python, Sed, Text
알렉스는 창고에서 어렸을 때 가지고 놀던 막대 N개를 찾았다. 막대의 길이는 A1, A2, ..., AN이며, 모두 2보다 크거나 같은 자연수이다.
오늘은 이 막대를 이용해서 직사각형을 만들려고 한다. 각 막대는 최대 한 번 사용할 수 있고, 여러 개의 막대를 이용해서 직사각형의 한 변을 만드는 것은 불가능하다. 일부 막대는 직사각형을 만들 때 사용하지 않아도 된다. 직사각형은 하나 이상을 만들어도 된다.
알렉스는 막대의 길이를 1만큼만 줄일 수 있는 기계를 하나 만들었다. 막대의 길이가 Ai라면, 막대의 길이를 Ai-1로 줄여서 사용할 수 있다. 기계를 사용하는 횟수는 제한이 없지만, 길이를 줄인 막대를 또 줄일 수는 없다.
알렉스는 만든 직사각형의 넓이의 합이 최대가 되게 직사각형을 만들려고 한다. 이 때, 그 넓이를 구하는 프로그램을 작성하시오.
입력 형식
첫째 줄에 막대의 개수 N(1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄에는 막대의 길이 A1, A2, ..., AN이 주어진다. (2 ≤ Ai ≤ 100,000)
출력 형식
알렉스가 만든 직사각형의 넓이의 합의 최댓값을 출력한다.
예제 입력 1
4
5 5 6 6예제 출력 1
30예제 입력 2
4
4 5 2 3예제 출력 2
8예제 입력 3
4
2 4 6 8예제 출력 3
0예제 입력 4
6
5 6 6 3 4 4예제 출력 4
24예제 입력 5
9
10 3 4 4 4 5 6 6 6예제 출력 5
42예제 입력 6
10
10 10 10 10 10 10 10 10 10 10예제 출력 6
200예제 입력 7
4
100000 100000 100000 100000예제 출력 7
10000000000
Comments