Excavación (2) P62226


Statement
 

pdf   zip

thehtml

Cuánto más profunda sea la mina, más mineral se podrá extraer, pero mayor resulta el coste de la excavación. Pero la situación es distinta a la del problema Excavación (1): el ayuntamiento donde está situada la mina te regala un vale con el que podrás excavar gratuitamente V metros en cualesquiera de las n explotaciones mineras de las que dispones, a repartir como más te convenga. Te pedimos que, conociendo el valor del mineral que se encuentra en los k primeros metros de cada explotaciones mineras, digas como repartir esos V metros de excavación gratuitos para obtener el máximo beneficio.

Entrada

Una entrada empieza con un número N≥ 0 en una línea, seguido de N casos de prueba. Cada caso de pruebas empieza con una línea con los valores k, n y V, seguido de n líneas de k valores cada una, donde el j-ésimo valor a de la i-ésima línea indica el valor del mineral que se encuentra a j metros de la superficie en la i-ésima explotación. Se te asegura que todos los valores a cumplen 0≤ a≤ 1000, y que 0<V≤ nk.

Salida

Para cada caso de pruebas, escribe en una línea el máximo beneficio que podrías obtener.

Puntuación

  • Test1:  ‍ Entradas con N<100 casos donde n es 1 o 2, y k≤ 10.  ‍25 Puntos ‍
  • Test2:  ‍ Entradas con N<100 casos donde n, k≤ 5.  ‍35 Puntos ‍
  • Test3:  ‍ Entradas con N<100 casos donde n, k≤ 40.  ‍40 Puntos ‍
Public test cases

  • Input

    6
5 1 5
1 0 0 1 0

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

5 2 5
1 3 0 1 1
4 0 0 0 9

5 3 5
1 2 1 1 1
0 0 0 9 1
4 1 7 0 1

5 3 5
1 2 1 1 1
0 0 0 9 1
1 1 6 0 1

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

    Output

    2
9
13
15
11
10

  • Input

    2
6 4 12
8 3 8 1 2 3
1 9 3 1 3 4
3 1 8 2 1 9
9 9 1 0 1 2

6 6 20
1 3 4 1 2 8
8 1 2 9 0 1
2 8 3 1 3 2
8 4 2 1 3 9
9 1 0 3 1 7
8 1 3 2 4 8

    Output

    64
95
    • Information
    Author
    Omer Giménez
    Language
    Spanish
    Official solutions
    C++
    User solutions
    C++