RoGN1 P78428


Statement
 

pdf   zip

html

El robot ro-GN1 (“Roñi”, para los amigos), originalmente diseñado para recoger restos de naufragios (joyas, monedas de oro, etc.), tuvo un accidente que le inutilizó el motor izquierdo. El robot puede desplazarse hacia arriba, hacia abajo, y hacia la derecha, pero nunca más podrá moverse a la izquierda, porque hace tiempo que dejaron de fabricarse piezas de recambio para reparar su lesión.

Sus nuevos amos lo usan ahora para limpiar el fondo de la piscina de un parque acuático, donde pasa largos días recogiendo la basura que dejan los niños. Sin embargo, Roñi fue programado para hacer su trabajo impecablemente: ayúdale a conseguirlo.

La base de la piscina es un rectángulo de n por m baldosas. En cada baldosa se encuentra una cierta cantidad de basura, que Roñi recogerá si pasa por encima de ella. Roñi no puede desplazarse hacia la izquierda, pero puede moverse arriba, abajo y a la derecha tantas veces como sea necesario. Deberás tener en cuenta que algunas baldosas están tan sucias que Roñi no puede ni limpiarlas ni cruzarlas, por temor a dañarse aún más. ¿Cuál es la cantidad máxima de basura que Roñi puede recoger?

Entrada

La entrada consiste de un número indeterminado de casos de prueba. Cada caso de pruebas empieza con una línea con tres números n>0, m>0 y k>1, que son las dimensiones n× m de la piscina y la máxima cantidad k de basura que puede tener una baldosa para que Roñi pueda pasar por encima suyo (y limpiarla en el proceso). A continuación, vienen n líneas con m números naturales cada una, describiendo la cantidad de basura que hay en cada baldosa. Únicamente habrá una casilla con 0 unidades de basura: aquella en la que se encuentra actualmente Roñi. Entre dos casos de prueba hay una línea en blanco.

Se te garantiza que ninguna entrada contendrá más de 100 casos de prueba, que ninguna baldosa tendrá más de 1000 unidades de basura, y que n,m≤ 200.

Salida

Para cada caso de pruebas, escribe la cantidad máxima de basura que Roñi puede recoger.

Puntuación

  • Test1:  20 Puntos 

    Resolver entradas con casos de prueba donde ninguna baldosa estará tan sucia que Roñi no pueda cruzarla, como el ejemplo 1.

  • Test2:  20 Puntos 

    Resolver entradas con casos de prueba con n=2 filas y m≤ 40 columnas, como el ejemplo 2.

  • Test3:  20 Puntos 

    Resolver entradas con casos de prueba con n=2 y n=3 filas y m≤ 40 columnas, como el ejemplo 3.

  • Test4:  20 Puntos 

    Resolver entradas con casos de prueba con n,m ≤ 40, como el ejemplo 4.

  • Test5:  20 Puntos 

    Resolver entradas con no más de 20 casos de prueba con n,m≤ 200.

Public test cases

  • Input

    4 6 5
1 2 3 1 1 2
0 3 1 2 1 1
3 5 1 2 1 2
3 1 2 3 1 1

4 6 5
1 2 3 1 1 2
1 0 1 2 1 1
3 5 1 2 1 2
3 1 2 3 1 1

4 6 5
1 2 3 1 1 2
1 3 1 2 1 1
3 5 1 2 1 2
3 1 0 3 1 1

4 6 5
1 2 3 0 1 2
1 3 1 2 1 1
3 5 1 2 1 2
3 1 2 3 1 1

4 6 5
1 2 3 1 1 2
1 3 1 2 1 1
3 5 1 2 0 2
3 1 2 3 1 1

4 6 5
1 2 3 1 1 0
1 3 1 2 1 1
3 5 1 2 1 2
3 1 2 3 1 1

    Output

    43
33
23
17
9
4

  • Input

    2 8 5
0 1 9 9 2 1 1 9 
1 1 2 1 1 9 1 2

2 8 5
1 0 9 9 9 1 1 9 
1 1 2 1 1 8 1 2

2 8 5
1 0 1 9 9 1 1 8 
1 9 2 1 1 1 9 8

2 8 5
1 0 9 9 9 1 1 8 
1 9 2 1 1 1 9 8

2 8 5
1 2 9 9 9 1 1 8 
1 0 9 1 1 1 9 8

    Output

    14
5
8
0
2

  • Input

    3 10 5
1 1 1 1 1 1 1 1 3 1
2 0 1 2 9 9 9 2 1 1
3 1 1 3 1 3 3 1 3 1

3 10 5
1 1 1 1 1 1 1 1 3 1
2 0 1 9 9 9 1 2 1 1
3 1 1 3 1 3 9 9 3 1

3 10 5
1 1 1 1 1 1 1 1 3 1
2 0 1 2 9 9 1 9 9 1
3 1 1 9 9 3 3 2 3 9

3 10 5
1 1 1 9 1 9 1 1 3 1
2 0 1 2 9 2 1 2 9 1
3 1 1 3 1 3 3 9 3 1

    Output

    32
23
21
30

  • Input

    4 5 5
0 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1

4 5 5
0 1 9 1 1
1 1 9 1 1
1 1 9 1 1
1 1 9 1 1

4 5 5
0 1 1 1 1
1 1 9 1 1
1 1 9 1 1
1 1 9 1 1

4 5 5
0 9 1 1 1
1 9 1 9 1
1 9 1 9 1
1 1 1 9 1

4 5 5
0 1 1 1 1
1 9 9 9 9
1 1 1 1 1
1 1 1 1 1

4 5 5
0 1 1 1 1
1 9 1 1 1
1 1 1 9 1
1 1 1 1 1

    Output

    19
7
16
13
11
15
    • Information
    Author
    Omer Giménez
    Language
    Spanish
    Official solutions
    C++
    User solutions
    C++