시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
3 초 (추가 시간 없음) | 1024 MB | 19 | 13 | 12 | 80.000% |
Uwaga. To zadanie różni się (nieznacznie) od zadania z tury otwartej: w tym zadaniu deski można dzielić, a nie tylko skracać.
Bajtek chce zbudować wielką, kwadratową piaskownicę. Do budowy piaskownicy są mu potrzebne zaledwie cztery deski, które muszą być równej długości. Niestety, podczas kupowania desek w tartaku Bajtek zupełnie zapomniał o tym fakcie i kupił N przypadkowych, niekoniecznie takich samych desek. Na szczęście Bajtek może – jeśli potrzebuje – podzielić część posiadanych desek na mniejsze kawałki, a następnie wybrać do budowy cztery kawałki równej długości. Na przykład, gdyby Bajtek miał deski o długościach 5, 2, 2, 2 i 1, może deskę o długości 5 podzielić na mniejsze, o długościach 2,3 (ale też np. 1,2,2), w wyniku czego będzie już mógł wybrać cztery deski o długości 2. Bajtek nie lubi ułamków, dlatego wszystkie długości desek są całkowite oraz wszystkie długości kawałków po podzieleniu również muszą być całkowite. Z drugiej strony chciałby jednak, żeby jego piaskownica była jak największa.
Napisz program, który wczyta długości desek posiadanych przez Bajtka, wyznaczy pole największej piaskownicy, którą może zbudować i wypisze wynik na standardowe wyjście.
W pierwszym wierszu wejścia znajduje się jedna liczba naturalna N (1 ≤ N ≤ 1 000 000), określająca liczbę desek posiadanych przez Bajtka. W drugim (ostatnim) wierszu wejścia znajduje się ciąg N liczb naturalnych L1, L2,. . . , LN (1 ≤ Li ≤ 109), pooddzielanych pojedynczymi odstępami. Są to długości desek posiadanych przez Bajtka.
W pierwszym (jedynym) wierszu wyjścia powinna się znaleźć jedna liczba całkowita – pole powierzchni największej możliwej do uzyskania kwadratowej piaskownicy zgodnie z warunkami powyżej. Jeśli zbudowanie takiej piaskownicy nie jest możliwe, należy wypisać 0.
7 4 10 3 4 2 1 2
16
4 1000000000 1000000000 1000000000 1000000000
1000000000000000000
3 7 13 36
144
1 1
0