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

Envío 4791

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

  • Autor: Ikerlb
  • Fecha: 2021-08-17 08:37:15 UTC (Hace más de 2 años)
Caso # Resultado Tiempo Memoria
#1
Error en tiempo de ejecución (NZEC) 
Exited with error status 1
Traceback (most recent call last):
  File "script.py", line 38, in <module>
    for _ in range(N):
TypeError: 'str' object cannot be interpreted as an integer
0.026 s 3 KBi
#2
Error en tiempo de ejecución (NZEC) 
Exited with error status 1
Traceback (most recent call last):
  File "script.py", line 38, in <module>
    for _ in range(N):
TypeError: 'str' object cannot be interpreted as an integer
0.021 s 3 KBi
#3
Error en tiempo de ejecución (NZEC) 
Exited with error status 1
Traceback (most recent call last):
  File "script.py", line 38, in <module>
    for _ in range(N):
TypeError: 'str' object cannot be interpreted as an integer
0.025 s 3 KBi
#4
Error en tiempo de ejecución (NZEC) 
Exited with error status 1
Traceback (most recent call last):
  File "script.py", line 38, in <module>
    for _ in range(N):
TypeError: 'str' object cannot be interpreted as an integer
0.027 s 3 KBi
#5
Error en tiempo de ejecución (NZEC) 
Exited with error status 1
Traceback (most recent call last):
  File "script.py", line 38, in <module>
    for _ in range(N):
TypeError: 'str' object cannot be interpreted as an integer
0.026 s 3 KBi
#6
Error en tiempo de ejecución (NZEC) 
Exited with error status 1
Traceback (most recent call last):
  File "script.py", line 38, in <module>
    for _ in range(N):
TypeError: 'str' object cannot be interpreted as an integer
0.024 s 3 KBi
#7
Error en tiempo de ejecución (NZEC) 
Exited with error status 1
Traceback (most recent call last):
  File "script.py", line 38, in <module>
    for _ in range(N):
TypeError: 'str' object cannot be interpreted as an integer
0.02 s 3 KBi
#8
Error en tiempo de ejecución (NZEC) 
Exited with error status 1
Traceback (most recent call last):
  File "script.py", line 38, in <module>
    for _ in range(N):
TypeError: 'str' object cannot be interpreted as an integer
0.029 s 3 KBi
#9
Error en tiempo de ejecución (NZEC) 
Exited with error status 1
Traceback (most recent call last):
  File "script.py", line 38, in <module>
    for _ in range(N):
TypeError: 'str' object cannot be interpreted as an integer
0.025 s 3 KBi
#10
Error en tiempo de ejecución (NZEC) 
Exited with error status 1
Traceback (most recent call last):
  File "script.py", line 38, in <module>
    for _ in range(N):
TypeError: 'str' object cannot be interpreted as an integer
0.029 s 3 KBi
#11
Error en tiempo de ejecución (NZEC) 
Exited with error status 1
Traceback (most recent call last):
  File "script.py", line 38, in <module>
    for _ in range(N):
TypeError: 'str' object cannot be interpreted as an integer
0.021 s 3 KBi
#12
Error en tiempo de ejecución (NZEC) 
Exited with error status 1
Traceback (most recent call last):
  File "script.py", line 38, in <module>
    for _ in range(N):
TypeError: 'str' object cannot be interpreted as an integer
0.02 s 3 KBi
#13
Error en tiempo de ejecución (NZEC) 
Exited with error status 1
Traceback (most recent call last):
  File "script.py", line 38, in <module>
    for _ in range(N):
TypeError: 'str' object cannot be interpreted as an integer
0.022 s 3 KBi
#14
Error en tiempo de ejecución (NZEC) 
Exited with error status 1
Traceback (most recent call last):
  File "script.py", line 38, in <module>
    for _ in range(N):
TypeError: 'str' object cannot be interpreted as an integer
0.023 s 3 KBi
#15
Error en tiempo de ejecución (NZEC) 
Exited with error status 1
Traceback (most recent call last):
  File "script.py", line 38, in <module>
    for _ in range(N):
TypeError: 'str' object cannot be interpreted as an integer
0.022 s 3 KBi
#16
Error en tiempo de ejecución (NZEC) 
Exited with error status 1
Traceback (most recent call last):
  File "script.py", line 38, in <module>
    for _ in range(N):
TypeError: 'str' object cannot be interpreted as an integer
0.025 s 3 KBi
#17
Error en tiempo de ejecución (NZEC) 
Exited with error status 1
Traceback (most recent call last):
  File "script.py", line 38, in <module>
    for _ in range(N):
TypeError: 'str' object cannot be interpreted as an integer
0.027 s 3 KBi
#18
Error en tiempo de ejecución (NZEC) 
Exited with error status 1
Traceback (most recent call last):
  File "script.py", line 38, in <module>
    for _ in range(N):
TypeError: 'str' object cannot be interpreted as an integer
0.03 s 3 KBi
Puntos totales: 0 / 100

Código

import math

def smsum(mat):
    N, M = len(mat), len(mat[0])
    for r in range(1, N):    
        mat[r][0] += mat[r - 1][0]         
    for c in range(1, M):    
        mat[0][c] += mat[0][c - 1]         
    for r in range(1, N):    
        for c in range(1, M):     
            mat[r][c] += mat[r - 1][c]     
            mat[r][c] += mat[r][c - 1]
            mat[r][c] -= mat[r - 1][c - 1]

def query(m, r1, c1, r2, c2):
    if r1 == c1 == 0:
        return m[r2][c2]
    if r1 == 0:
        return m[r2][c2] - m[r2][c1 - 1]
    if c1 == 0:
        return m[r2][c2] - m[r1 - 1][c2]
    return m[r2][c2] - m[r1 - 1][c2] - m[r2][c1 - 1] + m[r1 - 1][c1 - 1]

def max_submatrix(m):
    smsum(m)
    N, M = len(m), len(m[0])
    mx = -math.inf
    for r in range(N):
        for c in range(M):
            for rr in range(r + 1, N):
                for cc in range(c + 1, M):
                    mx = max(mx, query(m, r, c, rr, cc))
    return mx    

if __name__ == "__main__":
    N, M = input().split(" ")
    mat = []
    for _ in range(N):
        row = map(int, input().split(" "))
        mat.append(row)
    print(max_submatrix(mat))