Suma de productes P43645


Statement
 

pdf   zip

html

Donada una seqüència d’n naturals, l’heu de transformar en una suma de productes, de manera que el resultat sigui el màxim possible. Teniu dues restriccions:

  • No podeu modificar l’ordre relatiu dels elements.
  • Cap producte pot tenir més de tres factors.

Per exemple, el màxim resultat per a la seqüència 20, 12, 7, 10, 12, 1, 10, 40, 8 és 5001, corresponent a (20 · 12 · 7) + (10 · 12) + 1 + (10 · 40 · 8).

Entrada

L’entrada consisteix en diversos casos, cadascun amb un nombre n, seguit d’n naturals entre 1 i 104. Podeu suposar 1 ≤ n ≤ 105.

Sortida

Per a cada cas, escriviu el màxim resultat possible.

Public test cases

  • Input

    9  20 12 7 10 12 1 10 40 8
1  42
2  2 3
3  10 20 30
4  40 10 20 30
5  4 1 1 2 5
4  10000 10000 10000 10000

    Output

    5001
42
6
6000
8030
16
1000000010000
    • Information
    Author
    Salvador Roura
    Language
    Catalan
    Official solutions
    C++ Python
    User solutions
    C++