Camí de benefici màxim P32049


Statement
 

pdf   zip

thehtml

Considereu un tauler f × c, on cada casella té un valor positiu. Us trobeu a la casella de dalt a l’esquerra, i heu d’anar a la de baix a la dreta, sense sortir mai del tauler. Cada pas l’heu de fer cap a baix o cap a la dreta, amb una excepció: podeu fer s salts del cavall dels escacs (cadascun, de qualsevol de les vuit maneres possibles). Cada vegada que passeu per una casella n’acumuleu el valor. Optimitzeu el benefici.

Entrada

L’entrada consisteix en diversos casos. Cada cas comença amb f, c i s, seguit de f files amb c nombres naturals entre 1 i 105. Suposeu que f i c estan ambdues entre 3 i 100, i que s està entre 0 i 100.

Sortida

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

Public test cases
  • Input

    3 5 0
     2 20 20  3 20
     3  1  1  1  1
    50  2  5  1  4
    
    3 5 1
     2 20 20  3 20
     3  1  1  1  1
    50  2  5  1  4
    

    Output

    70
    130
    
  • Information
    Author
    Salvador Roura
    Language
    Catalan
    Other languages
    English
    Official solutions
    C++
    User solutions
    C++