guillotine.py

def g0(sx, sy, px, py, cache):
	if sx < min(px, py) or sy < min(px, py):
		return 0
	if sx*sy < px*py:
		return 0
	if sx*sy == px*py:
		return 1 if (sx==px and sy==py) or (sx==py and sy==px) else 0
	best = 0
	for i in range(1, sx):
		best = max(best, guillotine(i, sy, px, py, cache) + guillotine(sx-i, sy, px, py, cache))
	for i in range(1, sy):
		best = max(best, guillotine(sx, i, px, py, cache) + guillotine(sx, sy-i, px, py, cache))
	return best

def guillotine(sx, sy, px, py, cache):
	if (sx, sy) not in cache:
		cache[sx, sy] = g0(sx, sy, px, py, cache)
	return cache[sx, sy]

print(guillotine(300//5, 200//5, 55//5, 40//5, dict()))