Envío 995

Código

def get_integral_mat(mat):
    """
    Calculate integral matrix
    """
    nrows, ncols = len(mat), len(mat[0])
    sums_mat = [[0] * ncols for _ in range(nrows)]
    for i, row in enumerate(mat):
        for j, item in enumerate(row):
            ixy = mat[i][j]
            sx_1y = sums_mat[i][j-1] if j > 0 else 0
            sxy_1 = sums_mat[i-1][j] if i > 0 else 0
            sx_1y_1 = sums_mat[i-1][j-1] if i > 0 and j > 0 else 0
            sums_mat[i][j] = ixy + sx_1y + sxy_1 - sx_1y_1
    return sums_mat

def get_max_sum(mat):
    nrows, ncols = len(mat), len(mat[0])
    sums_mat = get_integral_mat(mat)
    max_sum = mat[0][0]
    for i in range(nrows):
        for j in range(ncols):
            for sub_i in range(i, nrows):
                for sub_j in range(j, ncols):
                    # calculate the sum using the integral matrix in O(1)
                    # doing s(a) - s(b) - s(c) + s(d) where a,b,c,d are the
                    # corners of the sub-matrix to be summed (in the original)
                    # matrix
                    s_a = sums_mat[i-1][j-1] if i > 0 and j > 0 else 0
                    s_b = sums_mat[i-1][sub_j] if i > 0 else 0
                    s_c = sums_mat[sub_i][j-1] if j > 0 else 0
                    s_d = sums_mat[sub_i][sub_j]
                    current_sum = s_a - s_b - s_c + s_d
                    if current_sum > max_sum:
                        max_sum = current_sum
    return max_sum

if __name__ == "__main__":
    nrows, ncols = list(map(int, input().split()))
    mat = [list(map(int, input().split())) for _ in range(nrows)]
    print(get_max_sum(mat))