Rei i joies P58851


Statement
 

pdf   zip

thehtml

El tresor d’un país llunyà és inicialment buit. Després, els funcionaris del tresor adquireixen algunes joies (cadascuna amb un cert valor) i les afegeixen al tresor d’una en una.

Segons una tradició antiga, el rei d’aquell país té el dret d’escollir i quedar-se fins a dos terços de les joies. Com que el rei pot haver de fugir del país en qualsevol moment, sempre necessita saber de forma eficient el valor màxim total de les joies que es pot endur. El podeu ajudar?

Entrada

L’entrada consisteix en diversos casos. Cada cas comença amb un natural n, el nombre de joies adquirides pel tresor. Segueixen els n valors de les joies, en l’ordre en què s’obtenen. Podeu assumir 1 ≤ n ≤ 104, i que els valors són enters entre 1 i 109.

Sortida

Per a cada cas, i després de cada joia adquirida, escriviu el valor màxim total de les joies que el rei pot triar. Escriviu una línia amb 10 guions després de cada cas.

Public test cases
  • Input

    6
    10
    42
    20
    23
    1000
    15
    
    8
    1000000000
    1000000000
    1000000000
    1000000000
    1000000000
    1000000000
    1000000000
    1000000000
    
    8
    7
    7
    6
    6
    7
    7
    6
    6
    

    Output

    0
    42
    62
    65
    1065
    1085
    ----------
    0
    1000000000
    2000000000
    2000000000
    3000000000
    4000000000
    4000000000
    5000000000
    ----------
    0
    7
    14
    14
    21
    28
    28
    34
    ----------
    
  • Information
    Author
    Salvador Roura
    Language
    Catalan
    Translator
    Salvador Roura
    Original language
    English
    Other languages
    English
    Official solutions
    C++
    User solutions
    C++