Suma de productes P43645


Statement
 

pdf   zip

thehtml

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++