Editorial for IOI '04 P4 - Phidias


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Use Dynamic Programming:

Let a(x, y) be the wasted area for a rectangle (x, y), 1 \le x \le W, 1 \le y \le H. Initially, put a(x, y) = xy, for all (x, y) except for the ones corresponding to needed plates, e.g. x = w_i and y = h_i, 1 \le i \le N, for which we put a(x, y) = 0. For a plate (x, y) consider all vertical cuts c = 1, 2, \dots, x-1 and all horizontal cuts c = 1, 2, \dots, y-1 and chose the cut producing the minimum wasted area a(x, y) = a(c, y) + (x-c, y) or a(x, c) + a(x, y-c) for some c.


Comments

There are no comments at the moment.