█████████ ████ ███░░░░░███ ░░███ ███ ░░░ ██████ ███████ ██████ ██████ ░███ ███░░███ ███░░███ ███░░███ ███░░███ ░███ ░███ ░███░███ ░███ ░███████ ░███ ░███ ░░███ ███░███ ░███░███ ░███ ░███░░░ ░███ ░███ ░░█████████ ░░██████ ░░████████░░██████ ░░██████ ░░░░░░░░░ ░░░░░░ ░░░░░░░░ ░░░░░░ ░░░░░░

Envío 1169

Problema 0xa6 - Submatriz de suma máxima en una matriz no muy grande

  • Autor: d4vsanchez
  • Fecha: 2020-10-11 06:14:55 UTC (Hace más de 3 años)
Caso # Resultado Tiempo Memoria
#1
Correcto
0.026 s 3 KBi
#2
Correcto
0.027 s 3 KBi
#3
Correcto
0.019 s 3 KBi
#4
Correcto
0.027 s 3 KBi
#5
Correcto
0.025 s 3 KBi
#6
Correcto
0.029 s 3 KBi
#7
Correcto
0.027 s 3 KBi
#8
Correcto
0.075 s 3 KBi
#9
Correcto
0.067 s 3 KBi
#10
Correcto
0.071 s 3 KBi
#11
Correcto
0.079 s 3 KBi
#12
Correcto
0.07 s 3 KBi
#13
Correcto
0.07 s 3 KBi
#14
Correcto
0.07 s 3 KBi
#15
Correcto
0.077 s 3 KBi
#16
Correcto
0.071 s 3 KBi
#17
Correcto
0.072 s 3 KBi
#18
Correcto
0.068 s 3 KBi
Puntos totales: 100 / 100

Código

def get_max_list(list_):
    answer = float("-inf")
    current_sum = 0
    for x in list_:
        current_sum = max(x, current_sum + x)
        answer = max(answer, current_sum)
    return answer

def compress_matrix(matrix, rows, columns):
    ans = float("-inf")

    for row in range(rows):
        sum_list = [0 for _ in range(columns)]
        for endRow in range(row, rows):
            for col in range(columns):
                sum_list[col] = sum_list[col] + matrix[endRow][col]
            ans = max(ans, get_max_list(sum_list))

    return ans

def main():
    matrix = []
    rows, columns = [int(x) for x in input().split()]

    for row in range(rows):
        column = [int(x) for x in input().split()]
        assert len(column) == columns
        matrix.append(column)

    ans = compress_matrix(matrix, rows, columns)
    print(ans)


if __name__ == '__main__':
    main()