306622: CF1223G. Wooden Raft

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Wooden Raft

题意翻译

你有n根木头,第i根长度为ai。 建造木筏需要 2根长度为x的木头和x根长度为y的木头,(2<=x,y) 你可以切割木头,但是不能将两个木头拼成一个,求木筏的最大面积(x*y)。

题目描述

Suppose you are stuck on a desert island. The only way to save yourself is to craft a wooden raft and go to the sea. Fortunately, you have a hand-made saw and a forest nearby. Moreover, you've already cut several trees and prepared it to the point that now you have $ n $ logs and the $ i $ -th log has length $ a_i $ . The wooden raft you'd like to build has the following structure: $ 2 $ logs of length $ x $ and $ x $ logs of length $ y $ . Such raft would have the area equal to $ x \cdot y $ . Both $ x $ and $ y $ must be integers since it's the only way you can measure the lengths while being on a desert island. And both $ x $ and $ y $ must be at least $ 2 $ since the raft that is one log wide is unstable. You can cut logs in pieces but you can't merge two logs in one. What is the maximum area of the raft you can craft?

输入输出格式

输入格式


The first line contains the only integer $ n $ ( $ 1 \le n \le 5 \cdot 10^5 $ ) — the number of logs you have. The second line contains $ n $ integers $ a_1, a_2, \dots, a_n $ ( $ 2 \le a_i \le 5 \cdot 10^5 $ ) — the corresponding lengths of the logs. It's guaranteed that you can always craft at least $ 2 \times 2 $ raft.

输出格式


Print the only integer — the maximum area of the raft you can craft.

输入输出样例

输入样例 #1

1
9

输出样例 #1

4

输入样例 #2

9
9 10 9 18 9 9 9 28 9

输出样例 #2

90

说明

In the first example, you can cut the log of the length $ 9 $ in $ 5 $ parts: $ 2 + 2 + 2 + 2 + 1 $ . Now you can build $ 2 \times 2 $ raft using $ 2 $ logs of length $ x = 2 $ and $ x = 2 $ logs of length $ y = 2 $ . In the second example, you can cut $ a_4 = 18 $ into two pieces $ 9 + 9 $ and $ a_8 = 28 $ in three pieces $ 10 + 9 + 9 $ . Now you can make $ 10 \times 9 $ raft using $ 2 $ logs of length $ 10 $ and $ 10 $ logs of length $ 9 $ .

Input

题意翻译

你有n根木头,第i根长度为ai。 建造木筏需要 2根长度为x的木头和x根长度为y的木头,(2<=x,y) 你可以切割木头,但是不能将两个木头拼成一个,求木筏的最大面积(x*y)。

加入题单

上一题 下一题 算法标签: