Submission #7087867

---

Source Code Expand

from itertools import product


w, h = map(int, input().split())
n = int(input())
xy_list = []
for i in range(n):
    x, y = map(int, input().split())
    xy_list += [(x - 1, y - 1)]


memo = [[[[-1] * (h + 1) for i in range(h + 1)] for j in range(w + 1)] for k in range(w + 1)]



def recur(left, right, lower, upper, machine_list):
    if machine_list:
        machine_list = [(x, y) for x, y in machine_list if left <= x < right and lower <= y < upper]
    if not machine_list:
        return 0
    ans = 0
    for x, y in machine_list:
        ret = (right - left) + (upper - lower) - 1
        for ((n_left, n_right), (n_lower, n_upper)) in list(product(((left, x), (x + 1, right)), ((lower, y), (y + 1, upper)))):
            if memo[n_left][n_right][n_lower][n_upper] != -1:
                ret += memo[n_left][n_right][n_lower][n_upper]
            else:
                ret += recur(n_left, n_right, n_lower, n_upper, machine_list)
        ans = max(ans, ret)
    memo[left][right][lower][upper] = ans
    return ans




print(recur(0, w, 0, h, xy_list))

Submission Info

Judge Result