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

Envío 1491

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

  • Autor: Serivt
  • Fecha: 2020-10-28 18:07:41 UTC (Hace alrededor de 4 años)
Caso # Resultado Tiempo Memoria
#1
Correcto
0.029 s 7 KBi
#2
Correcto
0.021 s 3 KBi
#3
Correcto
0.023 s 3 KBi
#4
Correcto
0.022 s 3 KBi
#5
Correcto
0.024 s 3 KBi
#6
Correcto
0.022 s 3 KBi
#7
Incorrecto
0.022 s 3 KBi
#8
Correcto
0.806 s 3 KBi
#9
Correcto
0.721 s 3 KBi
#10
Correcto
0.764 s 3 KBi
#11
Tiempo límite excedido
0.794 s 3 KBi
#12
Correcto
0.659 s 3 KBi
#13
Incorrecto
0.768 s 3 KBi
#14
Incorrecto
0.868 s 3 KBi
#15
Correcto
0.969 s 3 KBi
#16
Incorrecto
0.717 s 3 KBi
#17
Incorrecto
0.971 s 3 KBi
#18
Correcto
0.819 s 3 KBi
Puntos totales: 67 / 100

Código

import math
[r, c] = map(int, input().split())
m = []
for i in range(0, r):
    m += list(map(int, input().split(" ")))

max_sum = -math.inf

for r1 in range(0, r):
    for c1 in range(0, c):
        sub_sum = 0
        for r2 in range(r1, r):
            for c2 in range(c1, c):
                sub_sum += m[r2 * c + c2]
        max_sum = max(max_sum, sub_sum)
for r1 in range(1, r + 1):
    for c1 in range(1, c + 1):
        sub_sum = 0
        for r2 in range(0, r1):
            for c2 in range(0, c1):
                sub_sum += m[r2 * c + c2]
        max_sum = max(max_sum, sub_sum)
max_sum = max(max_sum, max(m))
print(max_sum)