Submission #7088071

---

Source Code Expand

import sys
import math
import collections
import itertools
from itertools import product

# Set max recursion limit
sys.setrecursionlimit(1000000)





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))



from collections import defaultdict
from heapq import heappush, heappop
import math
import bisect
import random
def LI(): return list(map(int, input().split()))
def I(): return int(input())
def LS(): return input().split()
def S(): return input()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
mod = 1000000007

Submission Info

Judge Result