Marek pracuje nad swoim edytorem grafiki, który posiada wiele interesujących funkcji. Dla każdej funkcji edytora stworzył on ikonę, będącą kwadratowym obrazkiem. Ikony te mają być rozmieszczone na pasku złożonym z dwóch wierszy i N kolumn.
Wysokość wiersza paska jest taka sama jak rozmiar największej ikony w wierszu.
Podobnie, szerokość kolumny jest taka sama jak rozmiar największej ikony
w kolumnie.
Wysokość paska to suma wysokości wszystkich wierszy.
Szerokość paska to suma szerokości wszystkich kolumn.
Marek zastanawia się, jak powinien rozmieścić ikony, żeby pole paska było
najmniejsze możliwe.
100 | 99 | 98 |
3 | 1 | 2 |
Dany jest posortowany ciąg liczb całkowitych s_1, ..., s_2N. Ciąg ten oznacza, że i-ta ikona ma wymiary s_i na s_i. Twoim zadaniem jest wyznaczenie najmniejszego pola paska, jakie może zostać osiągnięte.
Dla danych: 3 100 99 98 3 2 1 Poprawnym wyjściem jest: 30591 Jednym z optymalnych rozwiązań jest to przedstawione w treści zadania.
[Zgłoś rozwiązanie] [Moje zgłoszenia]