Sumas de matrices P81167


Statement
 

pdf   zip

thehtml

Consideremos una matriz de enteros tal que cada número tiene un valor entre -100 y 100. Se quiere calcular la suma máxima de la matriz siguiendo dos restricciones. La primera es que de cada fila como mucho se puede sumar un sólo número y la segunda es que si se suma el número de la fila i y columna j, cualquier número que se quiera sumar de una fila mayor que i tiene que ser de una columna mayor que j.

Entrada

La entrada contendrá un número indeterminado de casos. Cada caso constará de dos números N, M ≤ 100, el número de filas y columnas respectivamente.

Salida

Para cada caso imprimir la suma máxima de la matriz.

Public test cases
  • Input

    6 5
    -98 27 30 -48 -57
    56 -56 -51 90 96
    -24 -79 -82 76 -87
    -86 48 -24 20 4
    19 2 78 28 8
    -33 40 54 31 -56
    

    Output

    213
    
  • Input

    2 2
    -1 -1
    -1 -1
    

    Output

    0
    
  • Information
    Author
    Alex Alvarez
    Language
    Spanish
    Official solutions
    C++
    User solutions
    C++ Python