Editorial for IOI '04 P4 - Phidias - Olympiads Online Judge

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

Comments

There are no comments at the moment.