Suma de primers P45593


Statement
 

pdf   zip

thehtml

Cal partir un vector amb n nombres naturals en un o més trossos consecutius. Sigui ‍si la suma dels nombres del tros i-èsim. El valor de cada partició és la suma dels si que siguin nombres primers. L’objectiu és maximitzar aquest valor.

Entrada

L’entrada consisteix en diversos casos, cadascun amb n, seguida de @V[0]@, …@V[n-1]@. Suposeu 1 ≤ n ≤ 1000, que els nombres donats no són negatius, i que la suma dels nombres de cada cas no passa de 107.

Sortida

Per a cada cas, escriviu el valor de la millor partició possible.

Pista

Precalculeu eficientment abans de començar a llegir l’entrada un vector que indiqui quins nombres són primers i quins no.

Public test cases

  • Input

    1  2
2  3 8
3  1 7 1
5  4 6 0 8 10
3  27 2 9
3  3333373 3333296 3333331
2  9999990 1

    Output

    2
11
7
0
29
6666704
9999991
    • Information
    Author
    Salvador Roura
    Language
    Catalan
    Official solutions
    C++
    User solutions
    C++