Retiring replicants P85975


Statement
 

pdf   zip

html

It’s night and it’s raining. Rick Deckard is in the north-western house of a rectangular block of houses, crowded with replicants. Rick wants to “retire” (that is, kill) as many replicants as possible while going to the south-eastern house of the block. Rick can only move by jumping across the roofs of houses that are vertically or horizontally adjacent. When Rick enters a house, the ensuing fight to retire all replicants in the house causes so much destruction that he is just in time to leave the house before it collapses, so he cannot enter it anymore.


[rf]

Given a map with the number of replicants at each house, compute the number of replicants that Rick can “retire” while going from the north-western corner to the south-eastern corner, never repeating a house and always moving either horizontally or vertically.


[r]

Input

Input has several cases. Each case begins with the dimensions n × m of the map. Follow n rows with m positive integer numbers each. For every case, the sum of all its numbers is smaller than 109.

Output

For every case, print the maximum number of replicants that Rick can “retire”.

Public test cases
  • Input

    3 3
    1 2 3
    4 5 6
    7 8 9
    
    2 3
    7 1 7
    7 1 7
    
    2 2
    6 8
    9 7
    
    4 4
    16 13  8  1
    14  9  2  7
    10  3  6 11
     4  5 12 15
    

    Output

    45
    30
    22
    135
    
  • Information
    Author
    Albert Graells
    Language
    English
    Official solutions
    C++
    User solutions
    C++ Pascal
    Event
    Sisè Concurs de Programació de la UPC - Semifinal
    Date
    2008-06-28