Suma màxima P34239


Statement
 

pdf   zip

thehtml

Donats n naturals diferents, escolliu-ne un subconjunt de manera que la suma sigui màxima. Només teniu una restricció: per a tot parell x i y d’elements escollits, s’ha de complir | xy | ≥ d, on d és un natural donat.

Entrada

L’entrada consisteix en diversos casos, només amb enters. Cada cas comença amb n i d, seguits d’n nombres diferents. Suposeu 1 ≤ n ≤ 104, 1 ≤ d ≤ 105, i que els elements donats estan entre 1 i 105.

Sortida

Per a cada cas, escriviu la màxima suma possible.

Public test cases
  • Input

    1 100
    100000
    
    2 10
    30 40
    
    2 11
    30 40
    
    4 1
    1 2 3 4
    
    4 2
    1 2 3 4
    
    7 3
    47 27 25 44 48 30 28
    

    Output

    100000
    70
    40
    10
    6
    149
    
  • Information
    Author
    Salvador Roura
    Language
    Catalan
    Official solutions
    C++
    User solutions
    C++