Untitled
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