Untitled

mail@pastecode.io avatar
unknown
plain_text
a month ago
1.9 kB
4
Indexable
Never
def find_maximum_sum_of_beauties(grid, N):
    def compute_beauty(max_val, min_val):
        return max_val - min_val

    # Precompute min and max values for each sub-grid
    min_dp = [[[0] * N for _ in range(N)] for _ in range(N)]
    max_dp = [[[0] * N for _ in range(N)] for _ in range(N)]

    for size in range(N):
        for i in range(N - size):
            for j in range(N - size):
                min_val = float('inf')
                max_val = float('-inf')
                for x in range(i, i + size + 1):
                    for y in range(j, j + size + 1):
                        min_val = min(min_val, grid[x][y])
                        max_val = max(max_val, grid[x][y])
                min_dp[i][j][size] = min_val
                max_dp[i][j][size] = max_val

    max_sum_beauty = 0

    # Iterate over all possible sub-grids
    for size1 in range(N):
        for i1 in range(N - size1):
            for j1 in range(N - size1):
                beauty1 = compute_beauty(max_dp[i1][j1][size1], min_dp[i1][j1][size1])

                for size2 in range(N):
                    for i2 in range(N - size2):
                        for j2 in range(N - size2):
                            if (i1 <= i2 < i1 + size1 + 1 or i2 <= i1 < i2 + size2 + 1) or \
                               (j1 <= j2 < j1 + size1 + 1 or j2 <= j1 < j2 + size2 + 1):
                                continue

                            beauty2 = compute_beauty(max_dp[i2][j2][size2], min_dp[i2][j2][size2])

                            max_sum_beauty = max(max_sum_beauty, beauty1 + beauty2)

    return max_sum_beauty

# Input Reading
N = int(input().strip())
grid = [list(map(int, input().strip().split())) for _ in range(N)]

# Finding the maximum possible sum of beauties
result = find_maximum_sum_of_beauties(grid, N)
print(result)
Leave a Comment